8

First question here, so preemptive apologies if I've committed some faux-pas. Additionally, I am aware that this question is about possibly the micro-est of micro-optimizations ever, and "micro-optimization is the root of all evil" and all, but this question has been stuck in my mind for the past 3 weeks, and at this point I'm only asking so I can finally go back to sleeping soundly at night.

Background: I am creating my own Stack class in C++, implemented with a singly-linked list. One of the problems with a linked list is that each individual insertion and removal requires allocation and deallocation of memory. One of the tricks I'm using to reduce this issue is to allow the stack to cache a single, unused node. When an element is popped off the stack, if the cache is empty, the popped node is stored in the cache, rather than being deallocated. When an element is pushed onto the stack, if the cache has a node, the node is taken out of the cache and used to store the pushed element, rather than allocating a new node.

At most, only one node is ever cached at a time. When a node is popped off the stack while the cache already contains another node, one of these nodes must be deallocated. My question is: In this case, would it be better (for performance, memory, etc) for the stack to keep the cached node and deallocate the newly-popped node, or replace the cached node with the newly-popped node?

I can't think of any significant reasons why one option would be preferred over the other, since both nodes are functionally interchangeable. The only discerning factor that I can think of is the relative age of each node, and how that might affect their memory locations, which would thus affect memory fragmentation. With each pop from the stack, the newly-popped node would always be older than (was allocated before) the cached node, due to the LIFO nature of a stack meaning the youngest element is always removed (and thus cached) first. However, I'm not familiar enough with the gritty details of OS memory management to figure out how (or even if) this would affect anything.

TL;DR: Between two allocated blocks of memory, identical in all but age, where one must be deallocated and the other will be reused: Which should I choose to keep? Does it even matter which I choose?

4
  • Thanks for the tip, I've deleted the other question. Commented Jan 31, 2023 at 6:13
  • Are you sure a linked list is a good data structure for your application? Linked lists tend to be terrible for caches, in addition to the fragmentation problem. So is there some special reason for not just using a dynamic array?
    – JonasH
    Commented Jan 31, 2023 at 9:07
  • For my use case, I'm never looking past the top element, so I'm willing to trade iteration performance for (non-amortized) constant-time insertion and saving memory after a large contraction. I do agree that cache misses and fragmentation can be an issue, which is why I have each node hold a short array to store multiple elements. Admittedly, none of these are sizeable improvements, but the big reason I chose this was because I felt like trying it - this is part of a personal project to become more familiar with C++, so I'm mostly just messing around to see what I can do with the language. Commented Jan 31, 2023 at 10:16
  • I would suggest starting with a simpler vector-based solution, and benchmark this against any more complex implementation. I would not be surprised if the penalty due to allocations will outweigh most other performance concerns. But the important thing is to profile/benchmark, without this you are just making guesses with regards to performance. And even very experienced programmers often guess incorrectly.
    – JonasH
    Commented Jan 31, 2023 at 10:32

3 Answers 3

8

I think you might be getting way too complicated involving a memory pool with the style of caching you use just to optimize a linked list. It's starting to sound like an "object pool", and that's often a very inefficient and naïve approach in a language like C++ and especially in the context of implementing more efficient data structures where the elements in the data structure could be quite small and simple (there are contexts where something resembling "object pools" makes more sense, like thread pools given the cost of creating threads in an OS API, but not to optimize a general-purpose and lower-level data structure; that is to say that it's not so useful to optimize heap allocation/deallocation overhead to use something like "object pools" as opposed to object creation/destruction overhead).

I would recommend if you want to get knee-deep in custom allocators to just start studying some basic memory allocators like free lists and buddy allocators and slabs. Those can often allocate and free elements in constant time or close. The free list is often ideal for your purpose when you know the size of each element you're allocating in advance, especially if you can just toss away the allocator and purge all its allocated memory together with the linked structure. The others are generally variable-sized allocators that might allocate 16 bytes at one moment and 4 kilobytes the next, so they have far more complex and generalized requirements that usually cut into their ability to perform as effectively (not just in searching and fitting but placing commonly-accessed chunks next to each other in memory even if they're allocated one after the next) minus such demands.

But I would recommend even further to avoid custom memory allocators as often as possible to implement data structures, as they introduce a cumbersome separation between the data structure and allocator for it requiring both the implementer and users to deal with two detached things. That doesn't mean I recommend using default allocators or malloc and free for all your nodes, mind you.

What I mean is that you can usually get all the benefits of improved locality of reference and super fast constant-time allocation/deallocation without involving a custom allocator. For example, you can implement a linked list that stores elements of generic type T in C++ using std::vector that preserves O(1) insertion and removal of elements from anywhere in the linked lists. A diagram:

enter image description here

Apologies if this diagram is a bit cryptic. I dug it up from one of my old hard drives and it's something I illustrated to my colleagues about how we don't need to use custom allocators to implement an efficient linked list and can instead just use a random-access sequence. I had more words to go with the diagram in the original but I forgot what I said. But the basic idea is that allocators and data structures aren't that different from each other. Allocators just have the additional requirement that they have to pin some address, reference, or index, and make it immutable until it's freed. Unless you're trying to implement a data structure that can handle a variety of allocators, it's often a lot simpler to just implement the data structure efficiently in a way that doesn't need them. The first part of the diagram though is the linked list as is, the second demoing the removal of a node (in red), the third after removal when it becomes an entry in a free index list instead of the regular list, and the fourth and final image an illustration of the next insertion to the back of the list reclaiming that space.

In that case you'd store indices to elements rather than pointers for next/prev links in a node. That also tends to even beat the most efficient allocators on 64-bit architectures since you can generally shrink the indices to 32-bits or less (unless you need more than 2^32 elements in your list). A code snippet to illustrate:

    template <class T>
    class LinkedList
    {
    public:
        // Implementation left as an exercise to the reader.

    private:
        struct Node
        {
           // Stores indices to the previous and next nodes in either
           // the freed list (for unused nodes) or the prev/next nodes
           // in the actual list (for used nodes). We can use -1 or
           // some other integer to indicate the equivalent of a
           // nullptr.
           int32_t prev = -1, next = -1;

           // Stores the memory for the element. Use placement
           // new to construct the element in place and manual
           // dtor invocation to destroy.
           std::aligned_storage<sizeof(T), alignof(T)> elt;
        };
        // Stores all the nodes contiguously. This is effectively like
        // your node allocator except we're guaranteed a contiguous
        // rep and don't have to fiddle with custom allocators. You
        // can use different random-access containers here to suit
        // your specific needs. The only requirement is that they're
        // random-access via index and support inserting new nodes.
        std::vector<Node> nodes;

        // Stores the index to the head and tail of the linked list.
        // This is not so different from your vanilla pointer
        // implementation, but instead of *head or *tail to access
        // the 'pointees', you use 'nodes[head]' or 'nodes[tail]'.
        int32_t head = -1, tail = -1;

        // Stores the index to the first free node in the list. When
        // this is null (-1 in this case), you can push_back more
        // nodes and connect their links to the free list. When
        // you remove a node, you invoke the dtor on the element and
        // connect its links to effectively push it to this free index
        // list.
        int32_t free_head = -1;

        // Pops a free index from the list. Use this when inserting
        // nodes to know what node index to use and construct. This
        // is your metaphorical equivalent of allocating a node and
        // getting a node pointer, except we instead get a node index
        // into our vector. Use placement new on the results to
        // construct the C++ object: new(nodes[n].data) T(...);
        // to construct it after allocating it.
        int32_t pop_free()
        {
            if (free_head == -1)
            {
                // If the free list is empty, push a new node.
                free_head = nodes.size();
                nodes.push_back(Node{-1, free_head});
            }
            const int32_t n = free_head;
            free_head = nodes[n].next;
            return n;
        }

        // Pushes the nth node to the free index list. Use this when
        // removing nodes from the list. This is your metaphorical
        // equivalent of freeing the node, except we pass in its
        // index instead of a pointer. Invoke the destructor on the the
        // the element before calling this: ((T*)nodes[n].data)->~T()
        // to destroy it before we free it.
        void push_free(int32_t n)
        {
            nodes[n].next = free_head;
            free_head = n;
        }

        // The rest is your vanilla computer science linked list
        // implementation. You're just working with indices into
        // your vector rather than pointers. You can use this type
        // of solution with minimal adaptation for all linked
        // structures (singly-linked lists, doubly-linked lists,
        // trees, graphs, etc).
    };

A Note

One thing I've noticed in common with some developers I've worked with and even a mindset I had when I was much younger is the notion that heap/free store allocation/deallocation is so expensive. That's usually wrong, and it's a kind of wrong that isn't even necessarily intuitively pointed out when profiling our code unless you're specifically looking for things like cache misses. I mean if you are going to write a free list or arena alloc and benchmark it against malloc, of course you'll see much faster times at the micro level. We're really scraping metal there and noticing the most nuanced differences that don't necessarily manifest in the real world. But the bulkier reason that using such allocators can significantly improve performance over a more general-purpose allocator typically is not the search times to find a free chunk of memory, and later mark it as removed, but their ability to allocate elements more contiguously improving locality of reference.

Improving spatial and temporal locality is the key and so even for anyone insisting on getting knee deep trying to implement their own custom allocators, I would suggest remembering this as often as possible. A benchmark that just allocates and deallocates memory left and right is not necessarily an effective measurement of memory efficiency when it comes to access patterns, paging, and CPU cache. It's incomplete. You want to measure the times it takes to access the results as well, and often repeatedly, since the common usage pattern is to allocate a chunk of memory once and access it a lot before it's freed.

Finally

[Edit] In this process, I forgot to answer the gist of the question [I am becoming so old and senile these days -- hope people will forgive someone who can't even remember what they said 10 minutes ago these days]! If you are still using this technique, then the ideal choice is dependent upon access patterns and temporal locality since you're interacting with CPU cache concepts like LRU or whatever your architecture uses. "Frequent" vs. "infrequent" is perhaps the start of how to think about this, not "old" vs. "new". Something old that's going to be accessed a lot subsequently is going to generally take priority over something new that's going to be accessed infrequently. Age doesn't tell you that much about access patterns unless the design of your software is such that memory that hasn't been accessed in a long time is unlikely to be accessed much in the future. That could be a firm assumption in many cases and it's the best our hardware can typically do, but it's not always the case; sometimes you have data that the user hasn't touched for 5 minutes which they're suddenly going to do intensive processing on and you might have that extra knowledge of the software's design needs that the hardware lacks to exploit.

But I want to reinforce the above that if you're starting to think about LRU type of concepts seeking to implement a linked structure like a singly-linked stack, you're probably going to spend excessive time on it with worse results over one who uses, say, a free list or my recommended strategy of guaranteeing contiguous storage of nodes with index links between them in a random-access contiguous structure.

11
  • 2
    Thanks for the detailed answer, this is a lot of interesting information! I'll add a couple details about my use case that might help. For one, this isn't a general-purpose stack, I have a specific use case. I need a stack that can handle frequent fluctuations in size, usually small but sometimes large, over a long lifetime. Each node actually stores multiple elements in a short (7 per) contiguous array. The elements themselves are fairly small (shared_ptrs). Only the topmost element of the stack is ever accessed, so I'm not concerned about iteration performance (the stack is never copied). Commented Jan 31, 2023 at 2:54
  • 1
    Also, Stack Overflow won't let me upvote this answer until I get 4 more reputation, but just know that I'd upvote this if I could. Commented Jan 31, 2023 at 3:02
  • 1
    I'm not sure if a linked array is useful for this specific use case, like I said I'm only ever accessing the topmost element of the stack, which includes removal; I'm never removing elements from the middle of the list, so this would just end up being a normal vector-based stack with unnecessary bookkeeping. However, the idea of using a vector to store nodes of a linked list is novel to me, and I can think of other places in this project that might benefit from that sort of structure. I really appreciate the detailed posts, I've gained a lot more from this question than I thought I would! Commented Feb 1, 2023 at 4:25
  • 1
    @DaSpudLord Cheers! It's one thing I want to point out a lot to C++ devs who think of allocators and data structures as two separate things. We just need stable pointers to meet the requirement of an allocator, and an allocator is effectively a data structure with tight requirements to avoid invalidating pointers no matter what. We can loosen the requirements with indices or even user-defined types like iterators, which can allow memory addresses to change without invalidating indices or iterators. One case where things do get complicated though, even for a simple LIFO stack, is concurrency.
    – Anti Gamer
    Commented Feb 1, 2023 at 4:28
  • 1
    @DaSpudLord But I hope you will forgive me if I was a bit harsh about avoiding your current solution if you can, since I've walked in those same footsteps many years ago. And at least my results, in spite of working with really smart people and implementing their suggestions, was worse both in terms of hardware and maintainability than the types of solutions I am proposing now. It can help to change the overall strategy/perspective towards something more in line with "data structures" and "containers" and less the "allocators".
    – Anti Gamer
    Commented Feb 1, 2023 at 4:30
4

You should likely have a mild preference for freeing objects in a LIFO order, i.e. preferring to keep older objects. You should avoid caching allocations. You should consider whether you really need linked lists.

But all of this depends on the data access patterns you expect. With optimizations like introducing a cache there is no free lunch – we can only expect to make certain patterns faster on average, while accepting that other patterns will become slower.

Free()-order and memory fragmentation

Disclaimer: the allocator-specific parts of this answer are based on glibc (as typically used on Linux, as it was around 2022).

Rationale: the main allocation arena in glibc is stack-like – unless a suitable free chunk already exists, the main arena is grown and new chunks are split off from the end. After some intermediate chunks are freed, this can lead to holes or fragmentation. Consider this example:

+--------+---+--------------+---+--------------+
| in use | A | ... free ... | B | ... free ... |
+--------+---+--------------+---+--------------+
---> direction of growth

Here, chunk A is likely older than chunk B. Chunk B separates two free memory regions. If we were to free chunk A, B would still fragment the free memory region. If we free chunk B, then the free memory region can be consolidated and used by the allocator more flexibly. In a long-running application, avoiding memory fragmentation also helps with data locality.

Instead of age, you could use alternative heuristics:

  • since the glibc heap grows towards higher addresses, compare the pointers and free the one with higher address, keeping the one with the lower address
  • inspect the glibc chunk metadata to see whether the neighboring chunks are known to be free. However, this invokes undefined behaviour, and the chunk metadata layout can change between versions.

However freeing chunk B might not produce the intended effect. The glibc-allocator has multiple layers of caching. When you free a chunk, the free memory will not be consolidated immediately. There is a per-thread cache (“tcache”) and a global cache (“unsorted bin”). Consolidation only happens if the freed chunk was evicted from the tcache into the unsorted bin, and if there is an allocation request for a size that cannot be satisfied by a cached chunk. This is rare for many common access patterns.

Note also that the allocator's built-in caching means that in the following example, all loop iterations will likely get the same memory chunk for p, and the subsequent allocations will have negligible overhead:

for (int i = 0; i < N; ++i) {
  char* p = malloc(size);
  ...
  free(p);
}

If adding your own caching layer on top of the allocator, note that higher-level caches tend to defeat the performance of lower-level caches. Caches depend on access pattern that can be used for optimization heuristics. If a high-level cache handles all the “easy” cases, the lower-level cache will only get the cache misses for which there are no predictable access patterns. Thus, the contents of the lower-level cache will be mostly random and waste space.

A multi-level cache design can still be useful if there are hardware considerations (e.g. caches on RAM vs SSD), and for in-memory caches if the higher-level cache is small but fast, with the lower-level cache being larger but slower. The glibc allocator itself uses such a multi-level design, with the tcache being a thread-local array of linked lists (very fast, O(1) access), and the other allocator bins being doubly-linked lists that require a lock to be acquired (and may require unbounded amount of chunks to be traversed).

Adding your own caching could make sense e.g. if you are concered about the cost of the free() and malloc() function calls, since these calls cannot be inlined.

Effects of CPU caches

You should not be too concerned about the CPU caches. While reusing the same memory region is good for keeping the region in higher cache levels, data locality considerations may be overemphasized: the CPU cache doesn't care about whether two chunks of memory are near each other, only whether they share the same CPU cache line. Cache lines are generally 64 bytes large. Ideally, objects are aligned so that they do not unnecessarily cross cache line boundaries. To make good use of CPU caches, it tends to make sense to continue working with memory regions that have recently been touched. This could be an argument in caching the most recently freed node in your list since it is likely hot in the cache, whereas the previously cached value might be colder.

Where data locality considerations are essential is (a) making your data representation more compact to ensure that it fits into a cache line, and (b) helping the CPU predict which memory locations are loaded next. Linked lists are really bad at both of these.

Compact data representation. Linked lists rely on pointers, typically 64 bits (8 bytes) large. If we have a doubly-linked list and nodes in the list carry 8 bytes of data, then we can stuff 2 nodes into each cache line (1 forward pointer, 1 backward pointer, 8 bytes data, 8 bytes padding for alignment but actually needed for glibc allocator metadata). In contrast, an array doesn't need the pointers to the next node, and only needs space for the data – here being able to fit 8 items into the same cache line. A hybrid in form of an index list can also save some space. For example, if we limit ourselves to at most 2^32 nodes, then it would be sufficient to use a 4-byte index instead of a 8-byte pointer, giving us 4 nodes per cache line.

Cache prediction. Traversing a linked list requires a pointer to be dereferenced. This is difficult for the cache predictor to know, so traversing a linked list will lead to lots of cache misses (unless the other nodes already happen to be in the CPU cache). In contrast, traversing the elements in an array touches memory locations consecutively, possibly with some stride. This is very easy for the CPU to recognize, making it possible for the CPU to load the rest of the array into the CPU cache in advance.

These considerations mean that linked-list based data structures are typically an underperforming choice, unless you need guaranteed O(1) push/pop operations (and even that isn't guaranteed unless the node you insert has already been allocated). In contrast, growing an array usually requires moving its contents to a new location, which takes O(n) time. A push/pop to an array-based stack is still O(1) on average if you grow the array capacity exponentially, but this implies a space–time tradeoff. Any resize factor between 1× exclusive and 2× inclusive is reasonable, with 2× being common but wasting up to 50% of space (which might still be more space-efficient than the pointer overhead from linked lists).

In practice, data structure designers can often choose arbitrary tradeoffs between cheap insertion/removal versus flat data layouts by using techniques such as b-trees: nodes don't contain a single element but a small array. As the per-node arrays get smaller, the data structure approaches the characteristics of a linked list or binary tree. As the per-node arrays grow larger, the data structure approaches the behaviour of a single array, and the overhead of pointers between nodes is amortized across more items.

2
  • Nice answer! I'm going to quibble slightly about pushing "to an array-based stack is still O(1) on average if you grow the array capacity exponentially". The amortized cost is O(log n), logarithmic in current list size. (Sometimes folks will bound n with amount of RAM they can plug in, and then claim log n is constant with some hand waving). A nice treatment of related issues appears here: grantjenks.com/docs/sortedcontainers/performance-scale.html
    – J_H
    Commented Jan 31, 2023 at 19:10
  • @J_H Thanks! Yes, I do agree that claims of O(1) require a bit of handwaving in practice since they assume an idealized random-access machine. It no longer holds in cache-aware/external-memory models. BTrees are particularly attractive in such data models since they allow individual pages of the data structure to be loaded/cached independently, and are as such often used in databases and file systems.
    – amon
    Commented Jan 31, 2023 at 19:46
-1

two allocated blocks of memory, identical in all but age, where one must be deallocated and the other will be reused: Which should I choose to keep?

Keep the young one. Always. Locality of reference is important for performance, all up and down the memory hierarchy, and temporal locality certainly matters. There's paging to disk, and then there's L3 cache, and L2, and L1, and registers.

Discard the old block, thinking that it would lead to cache miss. Keep the younger, hoping it will enjoy one or more cache hits.


It's not clear that a caching layer belongs in your Stack abstraction.

Consider breaking the two apart, so each does just one thing.


Knuth asks us to bench, with stopwatch in hand, when we tack on what we believe are optimizations. Please add any such observations to the question or to a new answer.

2
  • Thanks for the answer, I hadn't considered CPU caching, that feels like an embarrassing oversight. In this case though, wouldn't the older block be more likely to still be in the CPU cache, since it was most recently used as the top element in the stack? Whereas the newer block would be the one in the stack's cache, which is unused, and therefore more likely to have been booted from the CPU cache? Commented Jan 31, 2023 at 6:21
  • The VM literature talks about "reference strings", or sequences of access. Paging to disk can evict pages in LRU order. If some level of memory hierarchy has e.g. 4-way associativity, we see a stochastic approximation of LRU evictions. In your setting we might have this sequence: push(value=3); pop(); pop(); pop(), with activity from this or other threads mixed in. We popped off 3, then 2, then 1. We anticipate that eventually another push will happen. What should now be cached? I claim the young "3" node should be cached, and we discard the old "2" and "1" nodes. It likely hasn't been evicted
    – J_H
    Commented Jan 31, 2023 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.