Return to Answer

This is the same idea applied as above. We're amortizing the cost of a linked list by designing a data structure that requires only paying that cost once per entire "collection" of elements, not per element. We're linking collections of elements not, not each and every element individually.

If you have to drive an hour just to get a cup of coffee, then the solution isn't necessarily to look for a faster car. It might be a whole lot easier if you just stock up on a month's worth of coffee instead. Design at a coarse level for bulk processing. That's the easiest way to reduce these costs paid on a per-object basis for teeny little objects.

This is the same idea applied as above. We're amortizing the cost of a linked list by designing a data structure that requires only paying that cost once per entire "collection" of elements, not per element. We're linking collections of elements now, not each and every element individually.

If you have to drive an hour just to get a cup of coffee, then the solution isn't necessarily to look for a faster car. It might be a whole lot easier if you just stock up on a month's worth of coffee instead, unless there's like a pretty girl working at the counter that you want to see each time, at which point you might look into a faster car. Design at a coarse level for bulk processing. That's the easiest way to reduce these costs paid on a per-object basis for teeny little objects.

Often using a different, coarser data structure will yield a nicer solution to maintain than one that calls for custom memory allocators. Similar case with how you design your classes. Memory allocators are kinda like reaching under the guts of your data types and structures, and it's always at least a little bit ugly and will never quite get you as far in terms of, say, minimizing memory use and maximizing processing efficiency. I'd consider designing different data types and using different data structures first whenever possible.

This is the same idea applied as above. We're amortizing the cost of a linked list by designing a data structure that requires only paying that cost once per entire "collection" of elements, not per element. We're linking collections of elements not, not each and every element individually. 

Memory allocators are kinda like reaching under the guts of your data types and structures, and it's always at least a little bit ugly and will never quite get you as far in terms of, say, minimizing memory use and maximizing processing efficiency. I'd consider designing different data types and using different data structures first whenever possible.

If you have to drive an hour just to get a cup of coffee, then the solution isn't necessarily to look for a faster car. It might be a whole lot easier if you just stock up on a month's worth of coffee instead. Design at a coarse level for bulk processing. That's the easiest way to reduce these costs paid on a per-object basis for teeny little objects.

Allocating each and every dog on a heap might be expensive. Allocating a container that could store a million dogs one time on the heap is not so expensive as that overhead is now reduced to 1/1,000,000. The easiest way to reduce the expense of allocating or freeing accessing or modifying a boatload of teeny objects is to avoid designing a boatload of teeny object types in the first place, and instead design a handful of bigger, coarser types of collection objects.

It's a similar thing for data structures. If you find you need to allocate too often with a linked structure, maybe an unrolled structure would be better, like an unrolled list:

Often using a different, coarser data structure will yield a nicer solution to maintain than one that calls for custom memory allocators. Similar case with how you design your classes.

Allocating each and every dog on a heap might be expensive. Allocating a container that could store a million dogs one time on the heap is not so expensive as that overhead is now reduced to 1/1,000,000. The easiest way to reduce the expense of allocating or freeing or accessing or modifying a boatload of teeny objects is to avoid designing a boatload of teeny object types in the first place, and instead design a handful of bigger, coarser types of collection objects.

It's a similar thing for data structures. If you find you need to allocate too often with a linked structure, maybe an unrolled structure would be better, like an unrolled linked list which is not storing one element per node, but many contiguous elements per node:

Often using a different, coarser data structure will yield a nicer solution to maintain than one that calls for custom memory allocators. Similar case with how you design your classes. Memory allocators are kinda like reaching under the guts of your data types and structures, and it's always at least a little bit ugly and will never quite get you as far in terms of, say, minimizing memory use and maximizing processing efficiency. I'd consider designing different data types and using different data structures first whenever possible.