8 deleted 8291 characters in body
source | link

My knowledge of how the internal garbage collector works in Java is limited, but I've been reading papers lately that shed some light on the subject.

The way Java allocates objects initially uses a strategy similar to a sequential memory pool. Sequential pool allocators tend to be extremely fast at a rapid burst allocation strategy of objects. For example, in C, one can often see anywhere from a 2x to 10x improvement in constructing a complex tree if the nodes are allocated using a sequential allocator rather than a general allocator (malloc).

That's the initial phase of allocation against the Java GC. It's very fast for rapid allocation of objects, possibly even getting close to rivaling stack allocation of objects in languages like C++ and very-possibly even beating naive attempts to call operator new or malloc per object in such languages without an efficient memory pool involved (fixed allocator, sequential allocator, etc).

The second phase is a bit more complex. After a single GC cycle of this kind of rapid, sequentially-allocated memory, the GC moves (copies) the memory contents of objects still referenced to a more persistent region of memory. This part is a bit of a performance gotcha, since performance-critical fields often need to focusDepends on concepts like spatial locality which ends up becoming lost if the memory contents of objects allocated together are then shuffled and dispersed in memory by a garbage collection cycle.

Object Pools

What does the above imply as far as object pools go? If the idea of using an object pool revolves around:

  1. Trying to allocate rapid bursts of objects faster, then it's very likely to actually contradict those goals and do more harm than good.
  2. Trying to improve spatial locality, then it's next to useless since the garbage collector will still rearrange the memory contents after an initial GC cycle for objects that survive (are still referenced) after one collection cycle.
  3. Trying to improve temporal locality in subsequent accesses, maybe it has some dim chance of improving read/write performance in critical loops for more complex objects.
  4. Trying to improve deterministic response/latency at the cost of throughput, then it might have some glimmer of a chance (ex: avoiding jarring stutters in frame rates in a video game but with the acknowledgement that the overall frame rate might get slower as a result of the pool even if the frame rate becomes more consistent/stable).
  5. Trying to reuse higher-level resource concepts and not the idea of the barebones object's memory (covered later), then it might have a good chance of helping.

Resource Pools

I'd distinguish "resource pools" from "object pools". For example, threads are very expensive to create in many operating systems (at the native level). A lot of libraries which distribute tasks repeatedly for various threads to process often use thread pools to avoid repeatedly paying the cost of creating and destroying threads.

While probably most Java developers wouldn't use a native thread API for this sort of thinking, imagine a scenario where they do. In that case, perhaps a thread is still modeled as an object.

Here using a thread pool is likely to help (which is pooling objects, but not for the typical reason of naively trying to avoid GC overhead). The pool here is not serving to avoid barebones object allocation/deallocation costs, but instead to avoid repeatedly initializing and destroying threads through the operating system.

In these cases where the resources associated to an object are very expensive to acquire (create) and release (destroy), then "object pools" might help a lot. Yet I wouldn't call them "object pools" anymore, since they're trying to resume using existing resources/states instead of trying to acquire a fresh object.

Data-Oriented Design

I often find myself citing data-oriented design as a solution to many performance-critical problems people encounter, but often I see people using object pools in areas like Java games when they will make their life a whole lot simpler and also get genuine, hard improvements in performance by applying data-oriented design instead.

Take this example:

class Particle
{
    ...
    private float size;
    private float x;
    private float y;
    private float z;
}

Someone might be tempted to pool this kind of Particle object as particles are born and die every few frames of a video game. An object pool is very unlikely to help here while making the code really dirty and harder to maintain.

Yet the real problem here is that the object-oriented design is being applied at too granular of a level. This translates to definite costs. For example, the size of a particle becomes 24 bytes instead of 16 in such a scenario, leading to more cache misses even in the lucky chance that multiple particles are right next to each other in memory and accessed prior to eviction. Yet any guarantees about spatial locality is effectively lost (we have no guarantees whatsoever that multiple particles will ever be anywhere close to each other in memory).

Instead by doing this:

class ParticleSystem
{
    ...
    private float[] xyzs = new float[n*4];
}

... we now have a contiguous AoS-style representation which has guaranteed spatial locality from one particle to the next, and no complex dynamics with temporal locality after an initial collection cycle. The size of each particle (at least ones that are accessed -- we might allocate more than necessary using chained pools of floating-point arrays) likewise shrinks down to 16 bytes, and more relevant particles then end up fitting into a 64-byte cache line (4 particles at once). An alternative to allow particles to be added and removed without an anticipated size in advance can be like this:

class ParticleSystem
{
    // How we represent things here doesn't matter so much. More
    // important is that we are designing our interfaces in a way
    // that leaves us room to change the underlying representation of
    // a collection of particles all we like.
    class ParticlePool
    {
        // has room for 128 particles.
        float[] xyzs = new float[128*4];

        // indicates whether a particle is used (can be tighter
        // using bits).
        boolean[] occupied = new boolean[128];

        // reference to next pool (initially null).
        ParticlePool next;
    }
    ...
    // Can use an array list with modulo 128 instead of singly-linked 
    // unrolled-style list if random-access is desired, can keep a list 
    // of free indices, etc. etc. etc. Most importantly, we can play with
    // this underlying representation all we like without breaking dependencies
    // to a ParticleSystem's public interface.
    private ParticlePool head = new ParticlePool;
}

This is not an object pool per se, but a "data" pool of plain old data represented contiguously through an array. It's almost certainly going to help if there's a heavy load here (ex: millions of particles being repeatedly accessed sequentially in critical loops). It's one possible strategy to optimize when dealing with a heavy load without reaching around the objects and trying to pool them individually.

If performance is a goal in cases where the barebones-style object pooling (not resource pooling) is a temptation, I'd suggest applying a data-oriented mindset. Design bulkier interfaces and objects, and you won't be trapped in a memory bottleneck interface design corner since your interfaces will give you a all the breathing room you need to iterate towards more efficient solutions like this.

Another example is to design Image interfaces instead of Pixel interfaces. If you have a million simple People entities you access in loops, design a People collection interface instead of a Person, e.g. This kind of data-oriented design approach will leave the breathing room you need to do all the optimization you need at the implementation level without breaking your designs, and without trying to pool little teeny objectscontext.

My knowledge of how the internal garbage collector works in Java is limited, but I've been reading papers lately that shed some light on the subject.

The way Java allocates objects initially uses a strategy similar to a sequential memory pool. Sequential pool allocators tend to be extremely fast at a rapid burst allocation strategy of objects. For example, in C, one can often see anywhere from a 2x to 10x improvement in constructing a complex tree if the nodes are allocated using a sequential allocator rather than a general allocator (malloc).

That's the initial phase of allocation against the Java GC. It's very fast for rapid allocation of objects, possibly even getting close to rivaling stack allocation of objects in languages like C++ and very-possibly even beating naive attempts to call operator new or malloc per object in such languages without an efficient memory pool involved (fixed allocator, sequential allocator, etc).

The second phase is a bit more complex. After a single GC cycle of this kind of rapid, sequentially-allocated memory, the GC moves (copies) the memory contents of objects still referenced to a more persistent region of memory. This part is a bit of a performance gotcha, since performance-critical fields often need to focus on concepts like spatial locality which ends up becoming lost if the memory contents of objects allocated together are then shuffled and dispersed in memory by a garbage collection cycle.

Object Pools

What does the above imply as far as object pools go? If the idea of using an object pool revolves around:

  1. Trying to allocate rapid bursts of objects faster, then it's very likely to actually contradict those goals and do more harm than good.
  2. Trying to improve spatial locality, then it's next to useless since the garbage collector will still rearrange the memory contents after an initial GC cycle for objects that survive (are still referenced) after one collection cycle.
  3. Trying to improve temporal locality in subsequent accesses, maybe it has some dim chance of improving read/write performance in critical loops for more complex objects.
  4. Trying to improve deterministic response/latency at the cost of throughput, then it might have some glimmer of a chance (ex: avoiding jarring stutters in frame rates in a video game but with the acknowledgement that the overall frame rate might get slower as a result of the pool even if the frame rate becomes more consistent/stable).
  5. Trying to reuse higher-level resource concepts and not the idea of the barebones object's memory (covered later), then it might have a good chance of helping.

Resource Pools

I'd distinguish "resource pools" from "object pools". For example, threads are very expensive to create in many operating systems (at the native level). A lot of libraries which distribute tasks repeatedly for various threads to process often use thread pools to avoid repeatedly paying the cost of creating and destroying threads.

While probably most Java developers wouldn't use a native thread API for this sort of thinking, imagine a scenario where they do. In that case, perhaps a thread is still modeled as an object.

Here using a thread pool is likely to help (which is pooling objects, but not for the typical reason of naively trying to avoid GC overhead). The pool here is not serving to avoid barebones object allocation/deallocation costs, but instead to avoid repeatedly initializing and destroying threads through the operating system.

In these cases where the resources associated to an object are very expensive to acquire (create) and release (destroy), then "object pools" might help a lot. Yet I wouldn't call them "object pools" anymore, since they're trying to resume using existing resources/states instead of trying to acquire a fresh object.

Data-Oriented Design

I often find myself citing data-oriented design as a solution to many performance-critical problems people encounter, but often I see people using object pools in areas like Java games when they will make their life a whole lot simpler and also get genuine, hard improvements in performance by applying data-oriented design instead.

Take this example:

class Particle
{
    ...
    private float size;
    private float x;
    private float y;
    private float z;
}

Someone might be tempted to pool this kind of Particle object as particles are born and die every few frames of a video game. An object pool is very unlikely to help here while making the code really dirty and harder to maintain.

Yet the real problem here is that the object-oriented design is being applied at too granular of a level. This translates to definite costs. For example, the size of a particle becomes 24 bytes instead of 16 in such a scenario, leading to more cache misses even in the lucky chance that multiple particles are right next to each other in memory and accessed prior to eviction. Yet any guarantees about spatial locality is effectively lost (we have no guarantees whatsoever that multiple particles will ever be anywhere close to each other in memory).

Instead by doing this:

class ParticleSystem
{
    ...
    private float[] xyzs = new float[n*4];
}

... we now have a contiguous AoS-style representation which has guaranteed spatial locality from one particle to the next, and no complex dynamics with temporal locality after an initial collection cycle. The size of each particle (at least ones that are accessed -- we might allocate more than necessary using chained pools of floating-point arrays) likewise shrinks down to 16 bytes, and more relevant particles then end up fitting into a 64-byte cache line (4 particles at once). An alternative to allow particles to be added and removed without an anticipated size in advance can be like this:

class ParticleSystem
{
    // How we represent things here doesn't matter so much. More
    // important is that we are designing our interfaces in a way
    // that leaves us room to change the underlying representation of
    // a collection of particles all we like.
    class ParticlePool
    {
        // has room for 128 particles.
        float[] xyzs = new float[128*4];

        // indicates whether a particle is used (can be tighter
        // using bits).
        boolean[] occupied = new boolean[128];

        // reference to next pool (initially null).
        ParticlePool next;
    }
    ...
    // Can use an array list with modulo 128 instead of singly-linked 
    // unrolled-style list if random-access is desired, can keep a list 
    // of free indices, etc. etc. etc. Most importantly, we can play with
    // this underlying representation all we like without breaking dependencies
    // to a ParticleSystem's public interface.
    private ParticlePool head = new ParticlePool;
}

This is not an object pool per se, but a "data" pool of plain old data represented contiguously through an array. It's almost certainly going to help if there's a heavy load here (ex: millions of particles being repeatedly accessed sequentially in critical loops). It's one possible strategy to optimize when dealing with a heavy load without reaching around the objects and trying to pool them individually.

If performance is a goal in cases where the barebones-style object pooling (not resource pooling) is a temptation, I'd suggest applying a data-oriented mindset. Design bulkier interfaces and objects, and you won't be trapped in a memory bottleneck interface design corner since your interfaces will give you a all the breathing room you need to iterate towards more efficient solutions like this.

Another example is to design Image interfaces instead of Pixel interfaces. If you have a million simple People entities you access in loops, design a People collection interface instead of a Person, e.g. This kind of data-oriented design approach will leave the breathing room you need to do all the optimization you need at the implementation level without breaking your designs, and without trying to pool little teeny objects.

Depends on the context.

7 Restored previous version
source | link

That pooling actually makes program performance worse especially in concurrent applications, and it is advisable to instantiate new objects instead, since in newer JVMs, instantiation of an object is really fast.

WorkingMy knowledge of how the internal garbage collector works in Java is limited, but I've been reading papers lately that shed some light on deleting my posts with positive answersthe subject. Going

The way Java allocates objects initially uses a strategy similar to trya sequential memory pool. Sequential pool allocators tend to be extremely fast at a rapid burst allocation strategy of objects. For example, in C, one can often see anywhere from a 2x to 10x improvement in constructing a complex tree if the nodes are allocated using a sequential allocator rather than a general allocator (malloc).

That's the initial phase of allocation against the Java GC. It's very fast for maximum negative votes!rapid allocation of objects, possibly even getting close to rivaling stack allocation of objects in languages like C++ and very-possibly even beating naive attempts to call operator new or malloc per object in such languages without an efficient memory pool involved (fixed allocator, sequential allocator, etc).

The second phase is a bit more complex. After a single GC cycle of this kind of rapid, sequentially-allocated memory, the GC moves (copies) the memory contents of objects still referenced to a more persistent region of memory. This part is a bit of a performance gotcha, since performance-critical fields often need to focus on concepts like spatial locality which ends up becoming lost if the memory contents of objects allocated together are then shuffled and dispersed in memory by a garbage collection cycle.

Object Pools

What does the above imply as far as object pools go? If the idea of using an object pool revolves around:

  1. Trying to allocate rapid bursts of objects faster, then it's very likely to actually contradict those goals and do more harm than good.
  2. Trying to improve spatial locality, then it's next to useless since the garbage collector will still rearrange the memory contents after an initial GC cycle for objects that survive (are still referenced) after one collection cycle.
  3. Trying to improve temporal locality in subsequent accesses, maybe it has some dim chance of improving read/write performance in critical loops for more complex objects.
  4. Trying to improve deterministic response/latency at the cost of throughput, then it might have some glimmer of a chance (ex: avoiding jarring stutters in frame rates in a video game but with the acknowledgement that the overall frame rate might get slower as a result of the pool even if the frame rate becomes more consistent/stable).
  5. Trying to reuse higher-level resource concepts and not the idea of the barebones object's memory (covered later), then it might have a good chance of helping.

Resource Pools

I'd distinguish "resource pools" from "object pools". For example, threads are very expensive to create in many operating systems (at the native level). A lot of libraries which distribute tasks repeatedly for various threads to process often use thread pools to avoid repeatedly paying the cost of creating and destroying threads.

While probably most Java developers wouldn't use a native thread API for this sort of thinking, imagine a scenario where they do. In that case, perhaps a thread is still modeled as an object.

Here using a thread pool is likely to help (which is pooling objects, but not for the typical reason of naively trying to avoid GC overhead). The pool here is not serving to avoid barebones object allocation/deallocation costs, but instead to avoid repeatedly initializing and destroying threads through the operating system.

In these cases where the resources associated to an object are very expensive to acquire (create) and release (destroy), then "object pools" might help a lot. Yet I wouldn't call them "object pools" anymore, since they're trying to resume using existing resources/states instead of trying to acquire a fresh object.

Data-Oriented Design

I often find myself citing data-oriented design as a solution to many performance-critical problems people encounter, but often I see people using object pools in areas like Java games when they will make their life a whole lot simpler and also get genuine, hard improvements in performance by applying data-oriented design instead.

Take this example:

class Particle
{
    ...
    private float size;
    private float x;
    private float y;
    private float z;
}

Someone might be tempted to pool this kind of Particle object as particles are born and die every few frames of a video game. An object pool is very unlikely to help here while making the code really dirty and harder to maintain.

Yet the real problem here is that the object-oriented design is being applied at too granular of a level. This translates to definite costs. For example, the size of a particle becomes 24 bytes instead of 16 in such a scenario, leading to more cache misses even in the lucky chance that multiple particles are right next to each other in memory and accessed prior to eviction. Yet any guarantees about spatial locality is effectively lost (we have no guarantees whatsoever that multiple particles will ever be anywhere close to each other in memory).

Instead by doing this:

class ParticleSystem
{
    ...
    private float[] xyzs = new float[n*4];
}

... we now have a contiguous AoS-style representation which has guaranteed spatial locality from one particle to the next, and no complex dynamics with temporal locality after an initial collection cycle. The size of each particle (at least ones that are accessed -- we might allocate more than necessary using chained pools of floating-point arrays) likewise shrinks down to 16 bytes, and more relevant particles then end up fitting into a 64-byte cache line (4 particles at once). An alternative to allow particles to be added and removed without an anticipated size in advance can be like this:

class ParticleSystem
{
    // How we represent things here doesn't matter so much. More
    // important is that we are designing our interfaces in a way
    // that leaves us room to change the underlying representation of
    // a collection of particles all we like.
    class ParticlePool
    {
        // has room for 128 particles.
        float[] xyzs = new float[128*4];

        // indicates whether a particle is used (can be tighter
        // using bits).
        boolean[] occupied = new boolean[128];

        // reference to next pool (initially null).
        ParticlePool next;
    }
    ...
    // Can use an array list with modulo 128 instead of singly-linked 
    // unrolled-style list if random-access is desired, can keep a list 
    // of free indices, etc. etc. etc. Most importantly, we can play with
    // this underlying representation all we like without breaking dependencies
    // to a ParticleSystem's public interface.
    private ParticlePool head = new ParticlePool;
}

This is not an object pool per se, but a "data" pool of plain old data represented contiguously through an array. It's almost certainly going to help if there's a heavy load here (ex: millions of particles being repeatedly accessed sequentially in critical loops). It's one possible strategy to optimize when dealing with a heavy load without reaching around the objects and trying to pool them individually.

If performance is a goal in cases where the barebones-style object pooling (not resource pooling) is a temptation, I'd suggest applying a data-oriented mindset. Design bulkier interfaces and objects, and you won't be trapped in a memory bottleneck interface design corner since your interfaces will give you a all the breathing room you need to iterate towards more efficient solutions like this.

Another example is to design Image interfaces instead of Pixel interfaces. If you have a million simple People entities you access in loops, design a People collection interface instead of a Person, e.g. This kind of data-oriented design approach will leave the breathing room you need to do all the optimization you need at the implementation level without breaking your designs, and without trying to pool little teeny objects.

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

That pooling actually makes program performance worse especially in concurrent applications, and it is advisable to instantiate new objects instead, since in newer JVMs, instantiation of an object is really fast.

My knowledge of how the internal garbage collector works in Java is limited, but I've been reading papers lately that shed some light on the subject.

The way Java allocates objects initially uses a strategy similar to a sequential memory pool. Sequential pool allocators tend to be extremely fast at a rapid burst allocation strategy of objects. For example, in C, one can often see anywhere from a 2x to 10x improvement in constructing a complex tree if the nodes are allocated using a sequential allocator rather than a general allocator (malloc).

That's the initial phase of allocation against the Java GC. It's very fast for rapid allocation of objects, possibly even getting close to rivaling stack allocation of objects in languages like C++ and very-possibly even beating naive attempts to call operator new or malloc per object in such languages without an efficient memory pool involved (fixed allocator, sequential allocator, etc).

The second phase is a bit more complex. After a single GC cycle of this kind of rapid, sequentially-allocated memory, the GC moves (copies) the memory contents of objects still referenced to a more persistent region of memory. This part is a bit of a performance gotcha, since performance-critical fields often need to focus on concepts like spatial locality which ends up becoming lost if the memory contents of objects allocated together are then shuffled and dispersed in memory by a garbage collection cycle.

Object Pools

What does the above imply as far as object pools go? If the idea of using an object pool revolves around:

  1. Trying to allocate rapid bursts of objects faster, then it's very likely to actually contradict those goals and do more harm than good.
  2. Trying to improve spatial locality, then it's next to useless since the garbage collector will still rearrange the memory contents after an initial GC cycle for objects that survive (are still referenced) after one collection cycle.
  3. Trying to improve temporal locality in subsequent accesses, maybe it has some dim chance of improving read/write performance in critical loops for more complex objects.
  4. Trying to improve deterministic response/latency at the cost of throughput, then it might have some glimmer of a chance (ex: avoiding jarring stutters in frame rates in a video game but with the acknowledgement that the overall frame rate might get slower as a result of the pool even if the frame rate becomes more consistent/stable).
  5. Trying to reuse higher-level resource concepts and not the idea of the barebones object's memory (covered later), then it might have a good chance of helping.

Resource Pools

I'd distinguish "resource pools" from "object pools". For example, threads are very expensive to create in many operating systems (at the native level). A lot of libraries which distribute tasks repeatedly for various threads to process often use thread pools to avoid repeatedly paying the cost of creating and destroying threads.

While probably most Java developers wouldn't use a native thread API for this sort of thinking, imagine a scenario where they do. In that case, perhaps a thread is still modeled as an object.

Here using a thread pool is likely to help (which is pooling objects, but not for the typical reason of naively trying to avoid GC overhead). The pool here is not serving to avoid barebones object allocation/deallocation costs, but instead to avoid repeatedly initializing and destroying threads through the operating system.

In these cases where the resources associated to an object are very expensive to acquire (create) and release (destroy), then "object pools" might help a lot. Yet I wouldn't call them "object pools" anymore, since they're trying to resume using existing resources/states instead of trying to acquire a fresh object.

Data-Oriented Design

I often find myself citing data-oriented design as a solution to many performance-critical problems people encounter, but often I see people using object pools in areas like Java games when they will make their life a whole lot simpler and also get genuine, hard improvements in performance by applying data-oriented design instead.

Take this example:

class Particle
{
    ...
    private float size;
    private float x;
    private float y;
    private float z;
}

Someone might be tempted to pool this kind of Particle object as particles are born and die every few frames of a video game. An object pool is very unlikely to help here while making the code really dirty and harder to maintain.

Yet the real problem here is that the object-oriented design is being applied at too granular of a level. This translates to definite costs. For example, the size of a particle becomes 24 bytes instead of 16 in such a scenario, leading to more cache misses even in the lucky chance that multiple particles are right next to each other in memory and accessed prior to eviction. Yet any guarantees about spatial locality is effectively lost (we have no guarantees whatsoever that multiple particles will ever be anywhere close to each other in memory).

Instead by doing this:

class ParticleSystem
{
    ...
    private float[] xyzs = new float[n*4];
}

... we now have a contiguous AoS-style representation which has guaranteed spatial locality from one particle to the next, and no complex dynamics with temporal locality after an initial collection cycle. The size of each particle (at least ones that are accessed -- we might allocate more than necessary using chained pools of floating-point arrays) likewise shrinks down to 16 bytes, and more relevant particles then end up fitting into a 64-byte cache line (4 particles at once). An alternative to allow particles to be added and removed without an anticipated size in advance can be like this:

class ParticleSystem
{
    // How we represent things here doesn't matter so much. More
    // important is that we are designing our interfaces in a way
    // that leaves us room to change the underlying representation of
    // a collection of particles all we like.
    class ParticlePool
    {
        // has room for 128 particles.
        float[] xyzs = new float[128*4];

        // indicates whether a particle is used (can be tighter
        // using bits).
        boolean[] occupied = new boolean[128];

        // reference to next pool (initially null).
        ParticlePool next;
    }
    ...
    // Can use an array list with modulo 128 instead of singly-linked 
    // unrolled-style list if random-access is desired, can keep a list 
    // of free indices, etc. etc. etc. Most importantly, we can play with
    // this underlying representation all we like without breaking dependencies
    // to a ParticleSystem's public interface.
    private ParticlePool head = new ParticlePool;
}

This is not an object pool per se, but a "data" pool of plain old data represented contiguously through an array. It's almost certainly going to help if there's a heavy load here (ex: millions of particles being repeatedly accessed sequentially in critical loops). It's one possible strategy to optimize when dealing with a heavy load without reaching around the objects and trying to pool them individually.

If performance is a goal in cases where the barebones-style object pooling (not resource pooling) is a temptation, I'd suggest applying a data-oriented mindset. Design bulkier interfaces and objects, and you won't be trapped in a memory bottleneck interface design corner since your interfaces will give you a all the breathing room you need to iterate towards more efficient solutions like this.

Another example is to design Image interfaces instead of Pixel interfaces. If you have a million simple People entities you access in loops, design a People collection interface instead of a Person, e.g. This kind of data-oriented design approach will leave the breathing room you need to do all the optimization you need at the implementation level without breaking your designs, and without trying to pool little teeny objects.

6 deleted 8441 characters in body
source | link

That pooling actually makes program performance worse especially in concurrent applications, and it is advisable to instantiate new objects instead, since in newer JVMs, instantiation of an object is really fast.

My knowledge of how the internal garbage collector works in Java is limited, but I've been reading papers lately that shed some light on the subject.

The way Java allocates objects initially uses a strategy similar to a sequential memory pool. Sequential pool allocators tend to be extremely fast at a rapid burst allocation strategy of objects. For example, in C, one can often see anywhere from a 2x to 10x improvement in constructing a complex tree if the nodes are allocated using a sequential allocator rather than a general allocator (malloc).

That's the initial phase of allocation against the Java GC. It's very fast for rapid allocation of objects, possibly even getting close to rivaling stack allocation of objects in languages like C++ and very-possibly even beating naive attempts to call operator new or malloc per object in such languages without an efficient memory pool involved (fixed allocator, sequential allocator, etc).

The second phase is a bit more complex. After a single GC cycle of this kind of rapid, sequentially-allocated memory, the GC moves (copies) the memory contents of objects still referenced to a more persistent region of memory. This part is a bit of a performance gotcha, since performance-critical fields often need to focusWorking on concepts like spatial locality which ends up becoming lost if the memory contents of objects allocated together are then shuffled and dispersed in memory by a garbage collection cycle.

Object Pools

What does the above imply as far as object pools go? If the idea of using an object pool revolves around:

  1. Trying to allocate rapid bursts of objects faster, then it's very likely to actually contradict those goals and do more harm than good.
  2. Trying to improve spatial locality, then it's next to useless since the garbage collector will still rearrange the memory contents after an initial GC cycle for objects that survive (are still referenced) after one collection cycle.
  3. Trying to improve temporal locality in subsequent accesses, maybe it has some dim chance of improving read/write performance in critical loops for more complex objects.
  4. Trying to improve deterministic response/latency at the cost of throughput, then it might have some glimmer of a chance (ex: avoiding jarring stutters in frame rates in a video game but with the acknowledgement that the overall frame rate might get slower as a result of the pool even if the frame rate becomes more consistent/stable).
  5. Trying to reuse higher-level resource concepts and not the idea of the barebones object's memory (covered later), then it might have a good chance of helping.

Resource Pools

I'd distinguish "resource pools" from "object pools". For example, threads are very expensive to create in many operating systems (at the native level). A lot of libraries which distribute tasks repeatedly for various threads to process often use thread pools to avoid repeatedly paying the cost of creating and destroying threads.

While probably most Java developers wouldn't use a native thread API for this sort of thinking, imagine a scenario where they do. In that case, perhaps a thread is still modeled as an object.

Here using a thread pool is likely to help (which is pooling objects, but not for the typical reason of naively trying to avoid GC overhead). The pool here is not serving to avoid barebones object allocation/deallocation costs, but instead to avoid repeatedly initializing and destroying threads through the operating system.

In these cases where the resources associated to an object are very expensive to acquire (create) and release (destroy), then "object pools" might help a lot. Yet I wouldn't call them "object pools" anymore, since they're trying to resume using existing resources/states instead of trying to acquire a fresh object.

Data-Oriented Design

I often find myself citing data-oriented design as a solution to many performance-critical problems people encounter, but often I see people using object pools in areas like Java games when they will make their life a whole lot simpler and also get genuine, hard improvements in performance by applying data-oriented design instead.

Take this example:

class Particle
{
    ...
    private float size;
    private float x;
    private float y;
    private float z;
}

Someone might be tempted to pool this kind of Particle object as particles are born and die every few frames of a video game. An object pool is very unlikely to help here while making the code really dirty and harder to maintain.

Yet the real problem here is that the object-oriented design is being applied at too granular of a level. This translates to definite costs. For example, the size of a particle becomes 24 bytes instead of 16 in such a scenario, leading to more cache misses even in the lucky chance that multiple particles are right next to each other in memory and accessed prior to eviction. Yet any guarantees about spatial locality is effectively lost (we have no guarantees whatsoever that multiple particles will ever be anywhere close to each other in memory).

Instead by doing this:

class ParticleSystem
{
    ...
    private float[] xyzs = new float[n*4];
}

... we now have a contiguous AoS-style representation which has guaranteed spatial locality from one particle to the next, and no complex dynamics with temporal locality after an initial collection cycle. The size of each particle (at least ones that are accessed -- we might allocate more than necessary using chained pools of floating-point arrays) likewise shrinks down to 16 bytes, and more relevant particles then end up fitting into a 64-byte cache line (4 particles at once). An alternative to allow particles to be added and removed without an anticipated size in advance can be like this:

class ParticleSystem
{
    // How we represent things here doesn't matter so much. More
    // important is that we are designing our interfaces in a way
    // that leaves us room to change the underlying representation of
    // a collection of particles all we like.
    class ParticlePool
    {
        // has room for 128 particles.
        float[] xyzs = new float[128*4];

        // indicates whether a particle is used (can be tighter
        // using bits).
        boolean[] occupied = new boolean[128];

        // reference to next pool (initially null).
        ParticlePool next;
    }
    ...
    // Can use an array list with modulo 128 instead of singly-linked 
    // unrolled-style list if random-access is desired, can keep a list 
    // of free indices, etc. etc. etc. Most importantly, we can play with
    // this underlying representation all we like without breaking dependencies
    // to a ParticleSystem's public interface.
    private ParticlePool head = new ParticlePool;
}

This is not an object pool per se, but a "data" pool of plain old data represented contiguously through an array. It's almost certainly going to help if there's a heavy load here (ex: millions of particles being repeatedly accessed sequentially in critical loops). It's one possible strategy to optimize when dealingdeleting my posts with a heavy load without reaching around the objects and trying to pool them individually.

If performance is a goal in cases where the barebones-style object pooling (not resource pooling) is a temptation, I'd suggest applying a data-oriented mindset. Design bulkier interfaces and objects, and you won't be trapped in a memory bottleneck interface design corner since your interfaces will give you a all the breathing room you need to iterate towards more efficient solutions like this.

Another example is to design Image interfaces instead of Pixel interfaces. If you have a million simple People entities you access in loops, design a People collection interface instead of a Person, e.gpositive answers. This kind of data-oriented design approach will leave the breathing room you need to do all the optimization you need at the implementation level without breaking your designs, and without tryingGoing to pool little teeny objects.try for maximum negative votes!

That pooling actually makes program performance worse especially in concurrent applications, and it is advisable to instantiate new objects instead, since in newer JVMs, instantiation of an object is really fast.

My knowledge of how the internal garbage collector works in Java is limited, but I've been reading papers lately that shed some light on the subject.

The way Java allocates objects initially uses a strategy similar to a sequential memory pool. Sequential pool allocators tend to be extremely fast at a rapid burst allocation strategy of objects. For example, in C, one can often see anywhere from a 2x to 10x improvement in constructing a complex tree if the nodes are allocated using a sequential allocator rather than a general allocator (malloc).

That's the initial phase of allocation against the Java GC. It's very fast for rapid allocation of objects, possibly even getting close to rivaling stack allocation of objects in languages like C++ and very-possibly even beating naive attempts to call operator new or malloc per object in such languages without an efficient memory pool involved (fixed allocator, sequential allocator, etc).

The second phase is a bit more complex. After a single GC cycle of this kind of rapid, sequentially-allocated memory, the GC moves (copies) the memory contents of objects still referenced to a more persistent region of memory. This part is a bit of a performance gotcha, since performance-critical fields often need to focus on concepts like spatial locality which ends up becoming lost if the memory contents of objects allocated together are then shuffled and dispersed in memory by a garbage collection cycle.

Object Pools

What does the above imply as far as object pools go? If the idea of using an object pool revolves around:

  1. Trying to allocate rapid bursts of objects faster, then it's very likely to actually contradict those goals and do more harm than good.
  2. Trying to improve spatial locality, then it's next to useless since the garbage collector will still rearrange the memory contents after an initial GC cycle for objects that survive (are still referenced) after one collection cycle.
  3. Trying to improve temporal locality in subsequent accesses, maybe it has some dim chance of improving read/write performance in critical loops for more complex objects.
  4. Trying to improve deterministic response/latency at the cost of throughput, then it might have some glimmer of a chance (ex: avoiding jarring stutters in frame rates in a video game but with the acknowledgement that the overall frame rate might get slower as a result of the pool even if the frame rate becomes more consistent/stable).
  5. Trying to reuse higher-level resource concepts and not the idea of the barebones object's memory (covered later), then it might have a good chance of helping.

Resource Pools

I'd distinguish "resource pools" from "object pools". For example, threads are very expensive to create in many operating systems (at the native level). A lot of libraries which distribute tasks repeatedly for various threads to process often use thread pools to avoid repeatedly paying the cost of creating and destroying threads.

While probably most Java developers wouldn't use a native thread API for this sort of thinking, imagine a scenario where they do. In that case, perhaps a thread is still modeled as an object.

Here using a thread pool is likely to help (which is pooling objects, but not for the typical reason of naively trying to avoid GC overhead). The pool here is not serving to avoid barebones object allocation/deallocation costs, but instead to avoid repeatedly initializing and destroying threads through the operating system.

In these cases where the resources associated to an object are very expensive to acquire (create) and release (destroy), then "object pools" might help a lot. Yet I wouldn't call them "object pools" anymore, since they're trying to resume using existing resources/states instead of trying to acquire a fresh object.

Data-Oriented Design

I often find myself citing data-oriented design as a solution to many performance-critical problems people encounter, but often I see people using object pools in areas like Java games when they will make their life a whole lot simpler and also get genuine, hard improvements in performance by applying data-oriented design instead.

Take this example:

class Particle
{
    ...
    private float size;
    private float x;
    private float y;
    private float z;
}

Someone might be tempted to pool this kind of Particle object as particles are born and die every few frames of a video game. An object pool is very unlikely to help here while making the code really dirty and harder to maintain.

Yet the real problem here is that the object-oriented design is being applied at too granular of a level. This translates to definite costs. For example, the size of a particle becomes 24 bytes instead of 16 in such a scenario, leading to more cache misses even in the lucky chance that multiple particles are right next to each other in memory and accessed prior to eviction. Yet any guarantees about spatial locality is effectively lost (we have no guarantees whatsoever that multiple particles will ever be anywhere close to each other in memory).

Instead by doing this:

class ParticleSystem
{
    ...
    private float[] xyzs = new float[n*4];
}

... we now have a contiguous AoS-style representation which has guaranteed spatial locality from one particle to the next, and no complex dynamics with temporal locality after an initial collection cycle. The size of each particle (at least ones that are accessed -- we might allocate more than necessary using chained pools of floating-point arrays) likewise shrinks down to 16 bytes, and more relevant particles then end up fitting into a 64-byte cache line (4 particles at once). An alternative to allow particles to be added and removed without an anticipated size in advance can be like this:

class ParticleSystem
{
    // How we represent things here doesn't matter so much. More
    // important is that we are designing our interfaces in a way
    // that leaves us room to change the underlying representation of
    // a collection of particles all we like.
    class ParticlePool
    {
        // has room for 128 particles.
        float[] xyzs = new float[128*4];

        // indicates whether a particle is used (can be tighter
        // using bits).
        boolean[] occupied = new boolean[128];

        // reference to next pool (initially null).
        ParticlePool next;
    }
    ...
    // Can use an array list with modulo 128 instead of singly-linked 
    // unrolled-style list if random-access is desired, can keep a list 
    // of free indices, etc. etc. etc. Most importantly, we can play with
    // this underlying representation all we like without breaking dependencies
    // to a ParticleSystem's public interface.
    private ParticlePool head = new ParticlePool;
}

This is not an object pool per se, but a "data" pool of plain old data represented contiguously through an array. It's almost certainly going to help if there's a heavy load here (ex: millions of particles being repeatedly accessed sequentially in critical loops). It's one possible strategy to optimize when dealing with a heavy load without reaching around the objects and trying to pool them individually.

If performance is a goal in cases where the barebones-style object pooling (not resource pooling) is a temptation, I'd suggest applying a data-oriented mindset. Design bulkier interfaces and objects, and you won't be trapped in a memory bottleneck interface design corner since your interfaces will give you a all the breathing room you need to iterate towards more efficient solutions like this.

Another example is to design Image interfaces instead of Pixel interfaces. If you have a million simple People entities you access in loops, design a People collection interface instead of a Person, e.g. This kind of data-oriented design approach will leave the breathing room you need to do all the optimization you need at the implementation level without breaking your designs, and without trying to pool little teeny objects.

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

5 added 12 characters in body
source | link
4 added 238 characters in body
source | link
3 added 597 characters in body
source | link
2 added 376 characters in body
source | link
1
source | link