If you don't know the size or bound, then do the next best thing and pre-allocate in chunks and use a slightly more sophisticated allocator that manages the chunks to hand out bits.

Not sure what mechanisms high-level languages use these days and whether there's any pre-allocation involved under the hood, but plain unoptimized linked lists can fragment your memory pretty badly and they also aren't cache coherent. Use them to store small #s of large objects, instead of large #s of small objects.

This means that even naive linked list implementations are typically much more cache efficient than you would expect coming from C, at least after a GC pass. It also means though that changes to the dependency graph of your program can have unexpected effects for your cache hit rates, since the compacting heuristics are pretty simple (they typically work by copying "child" objects immediately after the "parent" object, but there is no mechanism to define the "right" parent for an object)

Plus the pointer traversals are dependent loads. Until we load node->next, we don't know what address that is, so we cannot pre-fetch node->next->anything.

But when we access array[i], it's possible to pre-fetch array[i+1].

I'm still using linked lists because of the flexibility, functional substructure sharing and allocations you can avoid, but let's not kid ourselves.

But yes, linked lists are almost always worse than arrays, unless you're doing huge amounts of add/remove on large amounts of data.

From first principles, the biggest difference is that manual memory allocation can't move live objects around. But manual memory managers do still have the ability to be smart on deallocation, to the point that calling free will sometimes cause things to happen that would be similar in a garbage collector.

Of course locality is important even on single core cpus with no need for coherency.

What's the point of doing this again, manually? Or am I mistaken in my memory of the common modern malloc implementations?

General purpose tools are good for most cases. And being widely available they are cheaper too. Sometimes, however, you can do a better job with something special purpose tuned to the exact task at hand, but you have to buy the special purpose tool. The question is not IF it's better the question is whether it's worth the cost to you.

here are some things malloc can't do (afaik): - different pools for different parts (threads / datastructures / etc) of your app - better control over data locality - real time / non blocking allocations (i.e. low latency audio applications) - querying remaining available memory - releasing entire pools with a single call

I think the replies to your comment are unfairly giving you a hard time. Modern memory allocators are quite good. Before spending the time to roll your own allocation strategy, first do the experiments and analysis to convince yourself that memory allocation is even a performance problem. Once you've done that, do some work to implement a naive allocation strategy yourself and compare it against the standard allocator. If you're not outperforming it by a lot, work on it for a week. If after that week you're still not outperforming the standard allocator by a lot, just use the standard allocator.

Yes, sometimes optimizing for your exact use case can yield performance benefits. Buuuuuut... the chances that your use case actually falls out of what the general allocators have been designed for is small. And the people implementing the general purpose allocators are really good. They've optimized things you're not even aware of yet.

One random tidbit actually in favor of doing your own allocation: malloc and free are (in most compilers, I believe) always going to be function calls. Sometimes the benefit you get from rolling your own is just the benefit of eliminating a function call and inlining allocation code. ¯\_(ツ)_/¯

AFAIK also malloc will call sbrk quite a lot, at least from my cursory reading of this musl implementation[0].

[0] https://git.musl-libc.org/cgit/musl/tree/src/malloc/malloc.c...

Frequently you're working with hardware, devices, etc of which there's a limited number. I don't need a linked list to hold data for 3 peripherals. Even if the hardware is changed and the number changes and there's 10 peripherals I don't need a linked list. Sometimes an array is just fine.

  // Contiguous array of 1024 objects of type
  context = contextual_allocation(1024, sizeof type);

  // obtain pointer to next free object 
  object = allocate(context);

For example, the C++ Protocol Buffers library has an Arena class, which is documented here: https://developers.google.com/protocol-buffers/docs/referenc...

The EA STL has fixed_allocator, which implements a similar concept while exposing more low-level details in the API: https://github.com/electronicarts/EASTL/blob/master/include/...

An arena allocator is specifically optimized for incremental allocation and then bulk deallocation (the entire arena is freed at once).

The example code instead appears to create a context of a number of fixed sized blocks. Because of the fixed size, the allocator can make a lot of simplifying assumptions and generally achieve constant time algorithmic complexity, while allowing for individual allocations to be freed and reused.

This has a huge impact on the API design, so I don't think this can be retrofit in standard libraries of existing languages (because of backwards compatibility).

    int someFunctionThatAllocates(int A, int B, allocator const& alloc = default);

    {
        auto& alloc = james;
        if (someFunctionThatAllocates(4, 5)) // ok, uses 'alloc'
        {
        }
    }
    {
        if (someFunctionThatAllocates(4, 5, james)) // ok, uses 'james'
        {
        }
    }
    {
        auto& alloc1 = james;
        if (someFunctionThatAllocates(4, 5)) // error: no `alloc` in scope
        {
        }
    }

What's a Memory Allocator Anyway? by Benjamin Feng

https://www.youtube.com/watch?v=vHWiDx_l4V0

It can be very handy especially when you add tags to your allocation so you can track the number of allocations from a specific piece of code, great for finding memory leaks.

Yes. For linked lists this would typically mean creating a pool of objects to be allocated from the pool and returned to the pool as needed for operating the linked list.

Meaning: linked lists innately make most simple allocators more efficient.

Linked lists are a tradeoff between the difficulty of malloc/free (of which arrays are very difficult), and latency (of which linked lists have much higher latency).

A ton of 8-sized allocations is better on fragmentation than a 8-sized / 16-sized / 32-sized ... allocation pattern that most arary-allocators use.

Having (maybe?) more efficient malloc/free in exchange for dramatically increasing the cost of accessing your data is not a good trade-off for most access patterns.

See Chandler Carruth’s talk from CppCon 2014: https://youtu.be/fHNmRkzxHWs?t=2085

1 -> 2 -> 3 -> 4

Can become...

1 -> 2 -> 2.5 -> 3 -> 4

If you do that with arrays, you need a O(n) memcpy and maybe even a realloc.

-----------

Furthermore, linked lists don't even need a malloc routine !!!!!! See Knuth's dancing links (DXL) algorithm.

The ability to efficiently add and remove nodes from a linked list (even if that list was statically allocated) can sometimes beat the performance of arrays, because memcpy is just asymptotically slower than insert / remove.

Dancing Links seems to have outstanding performance for a generic cover problem, even on modern cache heavy processors.

It seems like the static layout of the links benefits greatly from cache locality. Seriously, study the algorithm before hating on it.

EDIT: Knuth's original writing style may be "too mathematical" for some. Here's a dumbed down version: https://medium.com/javarevisited/building-a-sudoku-solver-in...

The original Knuth: https://arxiv.org/abs/cs/0011047

The 2001 code is suboptimal in a few ways compared to the more recent updates. Knuth discusses the updates in Fasicle 6, the cweb source code is: https://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w

-------------------

EDIT: But... I hate it when people tell me to read other papers without pointing out the issue. :-)

The specific issue is that in Dancing Links: 1 -> 2 -> 3 becomes 1->3, and then later becomes 1 -> 2 -> 3 again. This pattern of insert (and then un-insert at the same place) means that all linked-list operations will execute in L1 cache.

Furthermore, Knuth lays out the data such that 1, 2, and 3 are sequential in memory. So the entire process is incredibly cache-efficient and takes advantage of both temporal and spatial locality. (Because 1 usually inserts / removes 2, and because 1 and 2 are always next to each other in memory, you're never leaving L1 cache).

As such, all DXL-operations are outstandingly fast. Furthermore, the pattern of insert-uninsert is useful for Exact Cover (which Knuth then used to solve graph coloring, N-Queens, Sudoku, and other NP-complete problems at relatively high speed). No, its not a generic SAT solver, but it does pretty darn good, especially considering how simple the operations are.

I didn't downvote your comments but memcpy is O(n) instead of O(1) : https://stackoverflow.com/questions/362760/how-do-realloc-an...

I'll delete this reply if you meant something else.

Yeah, I mean O(1) insert / remove for linked lists, and O(n) memcpys (most array insert / remove operations)

EDIT: I've edited my post above. I think its correct now. Thanks for pointing out the error.

The only thing a sorted linked list is really good for is being able to cheaply peek/pop the lowest- or highest-valued item, and a heap is almost always better for that use-case in practice.

Or cheaply peek/pop the middle items, and reinsert a middle item. As is the most common operation in Knuth's solution to the exact cover problem (aka: Dancing Links / Algorithm X)

There's also benefits to middle-operations, such as text editing (although text files are so small that inefficient operations aren't a big deal anymore).

----------

Linked Lists also can be "merged" together, in a sort of "inverse tree" sort of way.

Consider the following data: "ABCDEFG", "123ABCDEFG", and "111ABCDEFG".

The two array representations are obvious. But Linked-Lists can optimize that into:

* A -> B -> C -> D -> E -> F -> G

* 1 -> 1 -> 1 -> A ...

* 1 -> 2 -> 3 -> A ...

This has come up a lot for me in a recent toy problem I've been working on. A lot of sub-lists happen to be have the same "ending" as other lists, so I'm merging the linked lists and saving precious RAM (I'm building up GBs of data: so saving redundant chunks like this really wins)

Applications operating on text would normally use a rope (aka cord) or gap buffer. A linked list would have horrible performance because random access within the text is important for most applications.

> (I'm building up GBs of data: so saving redundant chunks like this really wins)

You’re likely spending a huge amount of memory to store pointers between elements within the unshared chunks (8 or 16 extra bytes per element adds up in a hurry) so it may be worth investigating some “chunking” so that you only have to use pointers to link between chunks, which can be stored continuously.

Alternatively, consider whether the index representation used by suffix arrays will work for your use-case: https://en.wikipedia.org/wiki/Suffix_array

> You’re likely spending a huge amount of memory to store pointers between elements within the unshared chunks (8 or 16 extra bytes per element adds up in a hurry) so it may be worth investigating some “chunking” so that you only have to use pointers to link between chunks, which can be stored continuously.

Yeah, they're chunked or unrolled in practice. (Unrolled Linked List was one term I've seen. Chunking is also another term).

> Alternatively, consider whether the index representation used by suffix arrays will work for your use-case: https://en.wikipedia.org/wiki/Suffix_array

Haven't heard of these before. But I'll look into it.

EDIT: Its... kind of a complicated situation I'm in. I'm basically searching a game tree, and building a "linked list" for how the children relate to their parent. I need "breadcrumbs" to relate any position back to the root.

Not necessarily because I need the root, but because the root contains information that's relevant to all of its children. So a linked list of (Grandchild -> child -> root) is very natural for this application. I originally had an array and just copied the data to an array (for "more locality") to all the children. But this uses way more space.

And the depth of this tree is ~12+, exponentially increasing width as usual. You really don't want to copy the root's data to all of the children unnecessarily: even on a GPU, its far better to just pass a pointer and connect the children-to-parent relationships, and traverse the linked list.

Hooking "child.parent = parent" is very easy. And traversing the while(node != root) node = node.parent; loop is also easy as cake. There's only ~12 of these linked-list operations in practice (because the depth of the search tree only goes to ~12 deep or so), across literally billions of possibilities. The billions of possibilities lead to the ability to process the tree in parallel (billions of possibilities to search with "only" 16384 hardware threads suddenly makes the GPU seem small!)

Despite the linked-list in the algorithm, its clear to me that the GPU is the ideal architecture for processing all of these nodes in parallel.

Growing the array from size 8 -> 16 -> 32 -> 64 ... 1024->2048 makes it harder, and harder to find contiguous, exponentially growing chunks.

If you have a fragmented memory allocator, you may run out of memory due to fragmentation. In contrast, if each of those elements were a small and constant-sized 8-byte chunk (or 16-byte chunk), then you'd be able to fit that small chunk anywhere.

-----------------

Anyway, I agree with you that vector.push_back() is an outstanding methodology on modern systems. But Linked-Lists aren't as bad as people make them out to be.

In tiny embedded devices with very limited memory, you do all your allocation at startup and avoid malloc during runtime, so you’d never run into this.

On server, desktop, or even smartphone applications, I’ve never run into cases where “the allocator was unable to get a chunk of memory to complete a vector resize()” is a significant problem. If my vector is going to be a significant fraction of the memory available on the system, I generally know that up-front, and would just call reserve() with a conservative estimate of the upper-found size. That’s pretty rare though - not many problems call for vectors that are 1+ GB in size. For anything that’s not a significant fraction of the system’s available memory, the allocator can generally find you a chunk.

Anyway, you run out of RAM really, really quickly if you try to give data-structures to each of those SIMD individually. 8GBs RAM / 16384-GPU-threads is 500kB per GPU-thread... 50kB at the theoretical max occupancy 10.

Yeah, you want your data-structures to be read-mostly so that your 16384-threads can all be reading the same stuff. But every now and then, you need a per-GPU-thread data-structure. And... well... there's not a lot of per-GPU-thread data available (because you have so many darn threads...)

--------

You end up using Linked lists, even though GPU latency is wtf terrible. Like really, really, really bad. If you think a CPU's 50-nanosecond DDR4 access time is slow, try 500ns or even 1000ns for a linked-list "node = node->next" operation on GPUs. And GPUs are in-order too, so no out-of-order latency hiding for you...

You mean like... going through a BVH tree to find what AABB bounding box collides with a ray? :-) I'm pretty sure its been demonstrated that GPUs are fastest at that.

Yeah, I know that linked lists take a latency hit. But even with that big hit, O(1) operations vs O(n) adds up. Don't avoid linked-lists, trees, or graphs just because you're trapped thinking about cache-locality or whatever.

A win in asymptotic complexity (especially O(1) vs O(n)) is utterly huge. On the one hand, its common for beginners to overestimate how much this matters. But on the other hand... its an asymptotic win. You gotta give it a shot.

Arrays win in many cases (and more cases in GPUs, because GPUs are worse at pointer chasing than arrays). Still, there are plenty of situations where the linked-list / tree / graph is simply unavoidable. Be it an oct-tree, linked list, or... BVH-tree traversals in Raytracing.

No, you can't do naïve recursion for this. GPUs just don't do that very well. But break it up with stream compaction, and everything is cake.

http://www.cse.chalmers.se/~uffe/streamcompaction.pdf

----------

Its not the memory-link latency that gets you here. Its branch divergence. Solve branch divergence, and then you're far faster than a CPU at traversing that BVH tree. Even without Raytracing Hardware. Even with lol 1000ns latency per node = node->next (GPUs turn out to be decent at latency hiding if you up that occupancy a bit... and just double-check on the compiler / assembly language stuff to ensure that the access was rearranged to a sane location).

I believe that GCC's libstdc++ tested the strategy on a set of real programs and didn't measure any actual difference so they still use doubling.

Memory mapping, pages and organization of the heap means that allocating as much memory in as few chunks as possible and reusing it if possible stands out when you profile the two different approaches.

Even if tiny chunks are allocated in their own arenas, the overhead of the allocation and dealing with the pointer it returns is still unnecessary compared to just dealing with the numbers on a loop through an array and moving on.

Not if you save the node you are working on. Inserting (when you have a node) is simply:

    NewNode = malloc(...) or new or something.
    NewNode.next = node.next
    node.next = NewNode

Lists will eventually become a problem since your next/prev pointers may not be pointing to adjacent memory positions, now your linear iteration over elements will not be cache friendly. Not only that but you need to retrieve pointers and dereference them, more pressure and worse for the cache again. You also add a "load" dependency between all elements so you can't easily break processing between multiple cores.

Lists may be conceptually elegant but they are not the most suited for performance or efficiency.

But what if they were pointing to adjacent memory positions in the common case? What if the problem you're suggesting doesn't exist in some circumstances?

Like in Knuth's Dancing Links. The neighbors of links are laid out in memory next to each other. If the list upon program startup is "1 -> 2 -> 3", we know that 1, 2, and 3 are neighbors in memory.

And what if it is demonstrated that this weird "linked list with nodes laid out next to each other" is shown to be sufficient to solve NP-complete problems like the exact-cover problem with great efficiency in practice?

-----------------

What if, when creating 100 nodes at a time, we lay out all 100-nodes in a row.

    chunk = malloc(sizeof(Node) * 100). 

    for(int i=99; i>=0; i--){
        chunk[i].next = head;
        chunk[i].data = foobar();
        head = chunk[i];
    }

More to the point of the discussion, it seems to me that you're describing situations where the cells of your container do have a natural inherent order, but may have additional relationships imposed on top of them. In the case of Algorithm X, the matrix has an inherent, consistent sense of order across rows and columns, but any particular line may skip elements depending on the state of the algorithm.

I think that doubly-layered structure is important to recognize; it's not something all data will have, and it's an inherent property of the problem or domain, not of the linked list data structure itself.

I'd like to respond more deeply but I'm not sure what to say, lol. You've just got a good post here so I feel like I should acknowledge it.

I don't know why you keep bringing this algorithm to the discussion, everything that was mentioned applies to any linked list. It's a fundamental property of linked lists, period.

Seems like you're completely missing the point: the discussion started on performance properties of data structures. That's what's being pointed out, and it's going to be a fact regardless of how you want to apply it.

> You also add a "load" dependency between all elements so you can't easily break processing between multiple cores.

You might be surprised.

Lets say we have that Node arrayOfNodes[100]. However, we do not know which node is the beginning, the end, which nodes are in the array, or which ones have been erased.

You might think that its an innately sequential algorithm to discover all the nodes in the array as well as its length. You'd be wrong: its a parallel algorithm, called Pointer Jumping.

https://en.wikipedia.org/wiki/Pointer_jumping

This "Pointer Jumping" methodology can be implemented on a GPU with high degrees of parallelism (one GPU-core per node), as long as you have enough nodes. In this arrayOfNodes[100] example, the parallelism is at best 100 (for example).

We can even perform order-dependent operations such as "prefix sum" over the arrayOfNodes, in parallel, while we are discovering the order of the nodes thanks to Pointer jumping. So in fact: it is very possible to operate linked lists in parallel (even SIMD / GPU parallel).

No, its not how the typical programmer traverses a linked list. But its a good trick for speeding things up in some circumstances.

A great example of pointer jumping is in the paper "Data Parallel Algorithms" by Hillis and Steele.

-----------

I'm not sure what your "3rd point" is. I only count two points.

> the discussion started on performance properties of data structure

The root of the discussion is a linked-list discussion. The literal text of the submission and title is: "Drop millions of allocations by using a linked list"

The point I make is that there's a great many tricks of Linked Lists that typical programmers don't seem to know about that mitigate the common complaints of linked-lists.

But there more optimized implementations of linked lists of course (probably using arrays as well internally (?)).

But computers aren't fast in allocating memory. In particular, they're not predictably fast in allocating memory, as most allocators will have complex internal data structures and may end up having to call the operating system to give fresh pages of unused memory. The best case may be smoking fast, the amortized cost may be decent but the worst case is pretty bad.

So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so.

And linked lists are still mighty fast in addition and removal, joining and splitting. Intrusive linked lists drop one extra pointer chase.

In kernel space, there are tons of use cases for linked lists that are never traversed, or at least not traversed in the fast path. Traversal is the slow part, but that's not necessary for a lot of cases where you add something to a list or a set, and remove items one by one.

There's no other data structure that beats linked lists when there's only addition, removal, joins and splits, but no traversals. Linked lists are almost always the wrong data structure for the job, but in special niche cases (which are not that rare, at least in kernel space) it's the simplest and most effective.

Template-based lists (in the style of C++ STL) let you have your cake and eat it too in that you still keep the list structure out of your data, but you still get the cache locality of an intrusive list.

boost.intrusive does, among other things, provide true intrusive lists and, for example, can insert the same node on multiple containers (not just lists) at the same time.

But really, no need for boost.intrusive, writing a templated intrusive list is not hard.

Don't get me wrong, I'm not saying one is better or worse, just that containers like std::list aren't better for every use-case you might have compared to an intrusive implementation. Perhaps I just misunderstood your "have your cake in eat it too" remark though.

Surely LLs are a poor example of this because _every_ newly created element becomes an allocation? The PR in the GP only managed to significantly reduce allocations because it was a particularly niche case and the PR was accidentally cheating.

My understanding from friends in the worlds where allocation matters is they use a lot of statically sized arrays.

The linux kernel uses intrusive linked lists (and intrusive rbtrees) a lot. They are the perfect data structure for a lot of uses where performance matters and allocations are a no go.

The linux kernel LL implementation uses kmalloc (i.e. it performs allocations) - although they get to dodge some of the problems of userspace allocators by using their own.

Here's the logic for adding a list node:

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
                                  struct list_head *prev,
                                  struct list_head *next)
    {
            if (!__list_add_valid(new, prev, next))
                    return;

            next->prev = new;
            new->next = next;
            new->prev = prev;
            WRITE_ONCE(prev->next, new);
    }

Static arrays are poor at joining, splitting, removal and merging.

O(1) joining, splitting and removal are of course not beatable by contiguous data structures.

True, but these are relatively rare requirements for a data container. My point isn't that LLs are totally useless but it seems like they'll see relatively little use if the goal is "no allocations at all".

This was when systems... often didn't even have cache memory at all. Accessing different RAM values took the same amount of time, and sometimes with a single clock cycle. Fast! So jumping around a (large, for the time) linked list in heap memory wasn't nearly as slow as something comparable today, relative to other data structures.

Ironically some of the ideas how to proceed with value types integration were already present in Eiffel, but so are design decisions.

https://en.wikipedia.org/wiki/Unrolled_linked_list

They ought to have quite good properties. In particular, if you are appending one element at a time, they never need to copy, but are also quite dense. Iteration is then fast. Feels like it should be useful for buffering and aggregation type jobs. I have never seen one in a library.

    data List a = Cons a (List a) | Nil

There's also some interesting work on flattened versions of arbitrary tree structures: https://engineering.purdue.edu/~milind/docs/ecoop17.pdf

They didn't explicitly ask for it to be unrolled, just sounded frustrated that I didn't make a fancy unrolled one. :)

Java's ArrayList was good enough in all cases, as was HashMap. Although one interesting thing, ConcurrentHashMap turned out to be faster in all my (bad) benchmarks.

I'm doing Go nowadays, it does not have generics except for its built in lists (arrays/slices) and maps, and that covers 99% of my use cases as well.

Anyway, I'll never work at Google or any company that does leetcode interviews because it's so far removed from (my?) reality.

I'm not sure what kinds of applications you're building, but if any of your collections contain on the orders of thousands/10s/100s thousands of items, you really should be considering the impact of how you shape that data for consumption inside your application. You hint at the need to do so, arraylists being good enough until they're not and then hashmaps, etc.

I think there is a pretty reasonable line between expecting our engineers and peers to pick proper containers for the data they're consuming without stepping over into purely 'academic' territory. Shutting down the discussions with 'well I've never had to use this' feels a bit icky and not a great way to advance any of the conversation.

Many years ago I worked on the early versions of an autocomplete app called SQL Prompt. It needed to be able to filter 1000s, 10000s, or 100000s of items to make completion suggestions without interrupting your typing. It still remains the only time in my 20 year career I've had to implement a trie, but it was absolutely the right data structure for that job.

Similarly I've used various kinds of tree and graph structures, different hashing schemes, and all kinds of other pointer - and even bit encoded - structures at different points in my career. It's very much in the minority of the work I've done, to the point where I definitely wouldn't do that well in an off the cuff leetcode interview, but I know what I need to look up when I come across a problem that might require a slightly more adventurous data structure or algorithm, and I've no qualms about using them.

People act like picking the right algorithm or data structure up front is too much effort or will take too long, and (this really grinds my gears) casually trot out that tired line about premature optimisation. You know what really takes too long? Figuring out why the system you spent 3 years building runs like absolute garbage in production when all your customers and stakeholders are screaming about it, and you're haemorrhaging sales because of it.

However I fully subscribe to not care to apply to companies that disregard professional experience in name of clever leetcode answers, completely irrelevant for the position one is applying for.

In other words, comprehensive knowledge of data structures won't be needed in 99% of the average career, no matter which company you working for.

Leetcode doesn't prove you're a good hire, it's just a lazy way of screening out bad hires (because the average applicant who can complete leetcode is going to be more competent than the average applicant who can't).

I can understand why big companies (Google scale) use leetcode in hiring - they want a scaleable method that filters out the bad candidates while leaving enough good candidates to pass through.

When you have 1000+ applicants for a job, you just need to trim the pool down to a manageable number of good candidates. As long as you end up with 20 good candidates, you don't care that you inadvertently screened out a further 100 good candidates in the process.

I still don't think it's an optimal method for hiring, but I at least understand why they do it.

How does one write software professionally without a solid grasp of data structures?

Occasionally, you might need to dig deeper to find an appropriate data structure for your specific use case (maybe something more exotic like a suffix or binary tree), but that's already pretty uncommon. Implementing a data structure from scratch? For the vast majority of developers, it's basically unheard of.

One exception to this though, IMO, is dynamic programming - while it's not something that someone like a web developer will need to know, it crops up so often once you go beyond that that I think it's a reasonable expectation (though not necessarily in a whiteboard scenario).

We had a code base maintained for almost 5 years that has to deal with one type of representation of data to another. The result form allows keeping combining two data points with some differences i.e. calls and arguments.

The combining the nodes and finding the differences happens as last step. It was just too much hassle to deal with comparison because, the initial form does not have much complexities but resultant form has much more complex datatypes. And we have to compare it with all potential things that could match. The complexity is inherent to the problem of comparing final representation.

Maybe it is obvious to other people here, but when I saw how the hashmap works, I was blown away. It is not just about having any datatype as index, it is about how efficiently you can find the index. It was about REDUCING THE EQUALITY CHECK. Because, it is costly, particularly when you are dealing with very deep tree nodes. That is where hash comes in.

So, we traversed the nodes once and created a signature of the structure that cannot be made into arguments and some other metadata determining its type i.e. hash. And we introduced an intermediate representation for effective comparison that is hybrid of initial and final representation. That sped things up so much. Now almost all the work of five years has to be thrown away.

I think such things exist in almost all projects. You would not know you need it, until you need it.

Edit: Added a point.

I actually solved a problem recently that I thought would require a QuadTree, and after implementing one and solving the problem I was proud of myself until I looked at the other solutions and realized I didn't need a QuadTree at all. In my notes I recorded the problem as a likely fail, because if I were the interviewer I'd take unnecessary complexity as a red flag. Part of me, I think, just wanted the chance to implement a QuadTree.

It's fairly simple: "qarrots" spawn nearby qarrots and get eaten when a "qabbit" collides with them; qabbits die if they get too hungry or old; qabbits in a certain age range colliding with each other spawn more qabbits; qarrots and qabbits inherit some attributes with slight mutation, so regional variations develop over time; and so on. I tweaked the parameters so that it's interesting to watch and neither the qarrots nor the qabbits dominate. This is not highly advanced software engineering, and if you've never wanted to do something like this, there is something wrong with the way you are living your life.

But the very simple O(NM) collision-detection scheme I'd used the other day to implement Space Invaders was too slow. With even a few thousand qarrots and a few hundred qabbits, I could only simulate like 4 time steps per second, which is ridiculous even given that JS in the browser is not the most performant platform. So now I'm doing a little bit of sorting ("broad-phase collision detection") to cut down on the number of object-to-object collision tests needed, and now performance is around 12–24 time steps per second, which makes the simulation way more fun. But faster would be better. I can afford about 15000 object–object collision tests per time step and still hit 60 time steps per second, but my simpleminded sorting algorithm is only cutting it down to about 20k–80k hit tests per time step, which is still a good improvement over four million or whatever it used to be.

I think that, if I use a grid ("spatial hash") and maybe update it incrementally, I should be able to hit 60 time steps per second. If I could get to higher numbers like 1000 or 10'000 time steps per second, I'd be able to see the impact of changed simulation parameters much more quickly. Alternatively, I could run much larger simulations, which might give rise to qualitatively different behavior—if the simulated world is too small, the qabbits tend to wipe out all the qarrots and then die out themselves.

ArrayList and HashMap and the Golang intrinsic containers don't really help much here. You probably don't need generics to solve it. But you do need to think about what data structure to use. Your years of professional experience avoiding such problems and posting anti-intellectual comments about how ignorance is just as good as knowledge, well, condolences, but you aren't going to convince these rectangular bunnies to simulate faster.

Isn't this not the case? My understanding was that 90% of HPC is normally about making sure to avoid as many individual allocations/deallocations possible, because these are massively expensive compared to almost all user-space operations, and lead to cache-inefficient memory layouts, which can slow your code down by like a factor of 200

It's about five machine instructions amortised.

Load the allocation pointer, add the object size to it, check it's not got too large, store it.

Deallocation though - yes that's slow!

In the real world, a malloc can involve picking an appropriate zone/arena based upon allocation size & the current thread, obtaining locks, chasing some pointers through its data structures, doing some book-keeping, perhaps even calling up to the OS to increase the process space.

Maybe in the very best case it can just shuffle a couple of pointers, but over time it has to do a lot more than that.

So the allocation fast path dominates your amortized allocation performance, even though the cases you're talking about are what dominate your worst-case performance.

See https://en.wikipedia.org/wiki/Amdahl%27s_law.

Well why wouldn't you?

> See https://en.wikipedia.org/wiki/Amdahl%27s_law

Allocation should be embarrassingly parallel in the fast path.

    $ sbcl
    This is SBCL 1.0.57.0.debian, an implementation of ANSI Common Lisp.
    ...
    * (defun nlist (n) (loop for i from 1 to n collect i))
    NLIST
    * (nlist 5)
    (1 2 3 4 5)
    * (compile 'nlist)
    NLIST
    NIL
    NIL

    * (time (dotimes (i 2000000) (nlist 500)))
    Evaluation took:
      6.477 seconds of real time
      6.460403 seconds of total run time (6.416401 user, 0.044002 system)
      [ Run times consist of 0.384 seconds GC time, and 6.077 seconds non-GC time. ]
      99.74% CPU
      18,093,926,186 processor cycles
      16,032,024,704 bytes consed

    NIL

The above is running on one core of a “Intel(R) Core(TM) i7-3840QM CPU @ 2.80GHz”, so if 18 processor cycles is not correct, it’s a damned good guess. Also, this CPU is from 02012, nine years ago.

What does this look like at the machine level? NLIST disassembles to 87 lines of assembly, so I’ll spare you most of it and excerpt only one of the allocations:

    * (disassemble 'nlist)
    ; disassembly for NLIST
    ; 029ECE7D:       488B4DF8         MOV RCX, [RBP-8]           ; no-arg-parsing entry point
    ...
    ;      EF9:       4D8B5C2418       MOV R11, [R12+24]
    ;      EFE:       498D4B10         LEA RCX, [R11+16]
    ;      F02:       49394C2420       CMP [R12+32], RCX
    ;      F07:       0F8696000000     JBE L9
    ;      F0D:       49894C2418       MOV [R12+24], RCX
    ;      F12:       498D4B07         LEA RCX, [R11+7]
    ;      F16: L4:   49316C2440       XOR [R12+64], RBP
    ...
    ;      FA3: L9:   6A10             PUSH 16
    ;      FA5:       4C8D1C2570724200 LEA R11, [#x427270]        ; alloc_tramp
    ;      FAD:       41FFD3           CALL R11
    ;      FB0:       59               POP RCX
    ;      FB1:       488D4907         LEA RCX, [RCX+7]
    ;      FB5:       E95CFFFFFF       JMP L4

In games it's common to use a similar pointer-bumping allocator for many allocations and then deallocate the whole heap at the end of the frame (by resetting the allocation pointer)—in that case, you don't even need the check against the heap limit, you just need to make sure you never come close to overflowing it. The Packrat-parsing backend of the project I'm working on at the moment, http://gitlab.special-circumstanc.es/hammer/hammer, does the same thing, but the arena is per-parse rather than per-frame, and it may be divided into multiple separately malloced blocks. Also, unlike SBCL, Hammer is in C, so it can't inline the calls to `h_arena_alloc`; they typically have to pay two instructions of argument setup, one instruction of function call, one instruction of return value handling, another instruction of PLT shared library overhead, and then the actual function is 26 instructions in the usual case.

The moral of the story is that the performance of fundamental operations depends strongly on the tradeoffs you make in your system design.

It's still true, though, that pointer-heavy data structures are terrible for cache locality (an L3 cache miss costs about 100 ns, as much as 15 allocations on one core, but typically the L3 cache is shared across all cores or at least all the cores on one socket), and that HPC consists mostly of large numerical arrays and not pointer chasing. Consequently, the software stacks used in HPC aren't optimized to make allocation cheap; they're optimized for other operations, and so they allow allocation to be expensive. I've explored this fascinating issue in somewhat more detail in http://canonical.org/~kragen/memory-models.

(It's a deeply damning commentary on the climate of boastful intellectual vacuity this site fosters that comments like this get downvoted for showing empirical evidence and comparing results from a wide variety of contexts, while confident but totally clueless comments about how an allocation necessarily involves acquiring locks and whatnot get voted up to the top. I guess they take less time to make!)

Realistically allocations mean mapping in more memory which is a system call, going to block and have both TLB and other cache effects. Every allocation will also need to be freed which needs to alter the heap data structure (there is a reason it's called the heap).

This idea that allocation is simple and fast is bizarre in any context where speed matters. The lowest hanging fruit to optimization is usually cutting down on allocations inside loops and just reusing a single allocation made ahead of time.

What this person was saying is true to an extent, although it is likely to be more in the ballpark of 5x to 10x slower instead of 200x.

I would not say minimizing allocations is a big part of HPC, I would say that it is the bare minimum to any non-trivial program where speed could be an issue.

In a generational copying system an object that is bump allocated and then is dead before being copied out of the young generation is indeed cheap - dead objects in the young generation don't need to be freed or even looked at in any way because the space for the young generation can simply be reused after everything is copied out of it. The slow part is elsewhere.

If lots of allocations are happening without freeing, more memory will have to be mapped in anyway on top of the constant pointer bumping - which means that a single allocation of an array would make sense instead.

If lots of allocations are happening with freeing, 'objects'/allocations will have to be moved around constantly to cater to the 'cheap' bump allocation.

If lots of allocations are happening then all being freed uniformly at the same time, it makes no sense to use lots of allocations since one array allocation would be fine.

Basically, making lots of tiny allocations marginally cheaper is a terrible strategy since it will always be a drag on performance since it is a naive and wasteful way to write software.

This is so trivially shown to be false that I suspect you are trolling. There is, for example, the situation I showed in https://news.ycombinator.com/item?id=26438596. Moreover, as gsg says, this is very generally true of pointer-bumping allocators in modern GCs; SBCL's GC isn't even all that modern.

The memory has already been mapped in (through a blocking system call) and it is contiguous. The "allocation" here is just the same uniform increment in an unbroken span of memory already in the process without taking into anything that makes memory allocation problematic for performance.

There is no point to the situation you described, it is a nonsense way to do something trivial. If that's what you want, allocate a single array.

The fact remains that memory allocation is often huge low hanging fruit for optimization. If it was 'just a few instructions' this would not be true. Garbage collection does not change this. You can read endless threads about 'performance java' people taking about allocating all their memory when their program starts and never inside their loops.

The reasons why have mostly been explained (system calls, heaps, copying in GCs, cache effects, TLB effects, etc.) though people have left out other nuances like mapped pages triggering interrupts on their first write to save time in the memory mapping call.

I think it will probably help to look into this further, thinking memory allocation is bumping a pointer is a simplification that will confuse any optimization until you understand it and profile.

I mean... it's how real allocators work in real VMs, so it's not nonsense, is it?

You originally said that memory allocation was 'just a few instructions' when the reality is that it is complex and avoiding allocation is the first thing to do when optimizing software.

Saying that memory allocation is simple and fast based on a scenario that should never happen because it's useless is a little silly. No, that is not how allocators work.

In modern language implementations with moving collectors allocation is literally what I've described in the fast path. Not theoretical. That's literally the instructions used.

> You originally said that memory allocation was 'just a few instructions'

Here it is in a real industrial compiler and garbage collector, for example.

https://github.com/oracle/graal/blob/f9530b0948c58a66845e84f...

It's precisely as I've described.

You are only on the 'fast path' when a single allocation of an array would have been much faster anyway. It isn't difficult to be 'fast' when accomplishing something trivial that would be even faster if done directly.

Why do you keeping saying the same thing while ignoring freeing memory, different lifetimes and wildly different sizes of allocations (which are why memory allocators actually exist)?

This idea that memory allocation is cheap is a blight on performance. Are you really allocating memory inside your hot loops and having it not show up when you profile?

Isn't that what I've said all along? I said 'amortised' in my very first comment. Most allocations are from the fast path... that's why they bother to make it fast.

> when a single allocation of an array would have been much faster anyway

TLAB allocation is heterogenous (which solves your size question.) An array isn't. TLAB can be evacuated and fragmention-free (which solves your lifetime problem.) An array can't.

> Why do you keeping saying the same thing while ignoring freeing memory

I said 'Deallocation though - yes that's slow!' in my very first comment.

Great example... because guess what happens with TLAB allocation during optimisation? It will do exactly what you say and combine multiple allocations into a simple bump, like it would with any other arithmetic!

> Anyone with experience optimizing knows this is not true ... Do you profile your programs? Do you work on optimizing them? I have a hard time believing you are doing something performance sensitive

I'm not going to keep arguing on this forever. But I have a PhD in language implementation and optimisation and I've be working professionally and publishing in the field for almost a decade. I'd be surprised to find out I have deep misconceptions on the topic.

It isn't a problem - I was responding to what you thought was a problem - having to bump multiple times in loop - that's what you asked me about? The bumps are tiny to start with, but even from that tiny start point they still get collapsed. You said collapsing them was important, so I showed you how that also happens.

> as I keep saying, anyone optimizing software knows that lots of small allocations are the first thing to look for

In some cases I've made code faster by putting allocations back in that other people removed without enough context on how allocation works and based on cargo culting of allocation being simply bad like you're pushing. Sometimes allocation is much better than reusing existing allocated space, due to reasons of spatial and temporal locality, cache obliviousness, escape analysis, publication semantics, coherence and NUMA effects, and more.

Mate I don’t know why you’ve gotten so worked up and aggressive about this.

But if you think I don’t know what I’m talking about despite all my work and publications on the subject then feel free to ignore me and go about your day happily.

There's Dunning–Kruger, and then there's Dunning–Kruger of the level "telling a guy whose Ph.D. dissertation, Specialising Dynamic Techniques for Implementing The Ruby Programming Language, is about code optimization on GraalVM, that he has a deep misconception, and questioning whether he has any experience optimizing".

I repeat my complaint about "the climate of boastful intellectual vacuity this site fosters."

I'm not really sure how anything I'm saying is even controversial unless someone is desperate for it to be.

Anyone who has profiled and optimized software has experience weeding out excessive memory allocations since it is almost always the lowest hanging fruit.

No matter how fast allocating a few bytes is, doing what you are ultimately trying to do with those bytes is much faster.

Allocating 8 bytes in 150 cycles might seem fast, until you realize that modern CPUs can deal with multiple integers or floats on every single cycle.

A 12 year old CPU can allocate space for, and add together well over 850 million floats to 850 million other floats in a single second on a single core. You can download ISPC and verify this for yourself. By your own numbers, the allocation alone would take about a minute and a half.

Neither of you has confronted this. I'm actually fascinated by the lengths you both have gone to specifically to avoid confronting this. Saying that lots of small allocations has no impact on speed is counter to basically all optimization advice and here I have explained why that is.

You're either misunderstanding, or pretending to misunderstand for some reason.

What I said was that allocating fresh objects and using those can be faster than re-using stale objects in some failed attempt to optimise by reducing allocations.

Why would that be? For the reasons I explained: The newly allocated objects are guaranteed to already be in cache. Each new object is guaranteed to be close to the last object you used, because they're allocated next to each other. The new objects are not going to need any memory barriers, because they're guaranteed to not be published. The new objects are less likely to escape, so they're eligible for scalar replacement.

You dismissed all that as 'throwing out terminology'.

Here's a practical example:

  require 'benchmark/ips'

  def clamp_fresh(min, max, value)
    fresh_array = Array.new
    fresh_array[0] = min
    fresh_array[1] = max
    fresh_array[2] = value
    fresh_array.sort!
    fresh_array[1]
  end

  def clamp_cached(cached_array, min, max, value)
    cached_array[0] = min
    cached_array[1] = max
    cached_array[2] = value
    cached_array.sort!
    cached_array[1]
  end

  cached_array = Array.new

  Benchmark.ips do |x|
    x.report("use-fresh-objects") { clamp_fresh(10, 90, rand(0..100)) }
    x.report("use-cached-objects") { clamp_cached(cached_array, 10, 90, rand(0..100)) }
    x.compare!
  end

It's actually the one that allocates a new object each time. The cached one is 1.6x slower in an optimising implementation of Ruby.

It's faster... but the only change I made was I added an object allocation instead of the custom object caching. I went from not allocating any objects to allocating an object and it became faster. This example is so clear because of the last factor I mentioned - scalar replacement.

If you came along and 'optimised' my code based on a cargo cult idea of 'object allocation disastrously slow' you wouldn't be helping would you?

I didn't claim he's an expert, but he did write TruffleRuby, which is still about twice as fast as any other implementation of Ruby six years later: https://pragtob.wordpress.com/2020/08/24/the-great-rubykon-b.... So I think it's safe to say that he's at least minimally competent at performance engineering :)

> I'm not really sure how anything I'm saying is even controversial

You're applying rules of thumb you've learned in one context in a context where they are invalid, and then you're accusing people who disagree with you of being ignorant or dishonest, even when it would take you literally 30 seconds to verify that what we're saying is correct, and where one of us literally has a doctorate in the specific topic we're discussing.

> Allocating 8 bytes in 150 cycles might seem fast

150 cycles doesn't sound terribly fast to me, though it'd be pretty good for malloc/free under most circumstances. I presented benchmark results from my 9-year-old laptop where LuaJIT did an allocation every 120 clock cycles, SBCL did an allocation every 18 cycles, and OCaml did an allocation every 9.5 cycles. You can easily replicate those results on your own machine. And that isn't the time for the allocation alone—it includes the entire loop containing the allocation, which also initializes the memory, and also the garbage-collection time needed to deallocate the space allocated. (And, in the OCaml case, it includes a recursive loop.)

chrisseaton says that in modern VMs like GraalVM an allocation is about 5 instructions, which I'm guessing is about 3 cycles.

(Incidentally on my laptop with glibc 2.2.5 malloc(16) and free() in a loop only takes about 18 ns, about 50 cycles, 55 million allocations per second. It took a little effort to keep GCC from optimizing away the loop. I wasn't satisfied until I'd single-stepped GDB into __GI___libc_malloc!)

120 cycles is less than 150 cycles. 18 cycles is a lot less than 150 cycles. 9.5 cycles is extremely much smaller than 150 cycles. 3 cycles, which I haven't verified but which sounds plausible, is smaller still.

> A 12 year old CPU can ... add together well over 850 million floats to 850 million other floats in a single second on a single core ...By your own numbers, the allocation alone would take about a minute and a half.

You're completely wrong about "By your own numbers."

It's surely true that you aren't going to get SIMD-like performance by chasing pointers down a singly-linked list of floating-point numbers (is that what you're suggesting?) but not because you can only allocate 10 million list nodes per second; it's because you'll trash your cache with all those worthless cdr pointers, the CPU can't prefetch, and every cache miss costs you a 100-ns stall, which often ties up your entire socket's memory bus, as I specifically pointed out in https://news.ycombinator.com/item?id=26438596. It's true that if you use malloc you'd need a minute or two (and 30 gigabytes!) to allocate 850 million such nodes, or maybe three minutes and 60 gigabytes to allocate two such lists. But if you use the kind of allocator we're talking about in this thread, you can do that much allocation in a few seconds rather than a few minutes, although it's still not a good way to represent your matrices and vectors.

> Neither of you has confronted this.

Well, no, why would we? It's just a silly error you made. Before you made it there was no way to confront it.

> Saying that lots of small allocations has no impact on speed is counter to basically all optimization advice

Allocations aren't zero-cost, even when multiple allocations in a basic block get combined as chrisseaton says GraalVM does, unlike any of the three systems I presented measurements from; at a minimum, allocating more requires the GC to run more often, and you need to store a pointer somewhere that points at the separate allocation. (Though maybe not for very long.) As I mentioned in my other comment, I've written a popular essay exploring this topic at http://canonical.org/~kragen/memory-models.

But the time required to allocate a few bytes can vary over two or three orders of magnitude, from the 3.4 ns I got with OCaml (or maybe 1 ns if several allocations get combined), up to the 43 ns I got with LuaJIT, up to the 100 ns malloc/free typically take, up to the 200 ns we're suffering in Hammer, up to the maybe 1000 ns you might get out of a bad implementation of malloc/free, up to maybe several microseconds on a PIC16 or something.

If you're trading off a 5-nanosecond small allocation against a 20-nanosecond L2 cache miss, you should probably use the allocation, although questions like locality of reference down the road might tip the balance the other way. If you're trading off a 100-nanosecond small allocation against a 20-nanosecond L2 cache miss, you should take the cache miss and remove the allocation. If you're trading off a 7-nanosecond small allocation in SBCL against triggering a 10000-nanosecond write-barrier by way of SBCL's SIGSEGV handler, you should definitely take the small allocation.

So, whether lots of small allocations speed your code up or slow it down depends a lot on how much small allocations cost, which depends on the system you're running on top of and the tradeoffs it's designed for.

You're familiar with a particular set of architectural tradeoffs which make small allocations pretty expensive. That's fine, and those tradeoffs might even be in some sense the objectively best choice; certainly they're the best for some range of applications. But you're mistakenly assuming that those tradeoffs are universal, despite overwhelming evidence to the contrary, going so far as to put false words in my mouth in order to defend your point of view. Please stop doing that.

Ruby runs 50x to 100x slower than native software, let alone well optimized native software. It is not a context that makes sense when talking about absolute performance.

> despite overwhelming evidence to the contrary,

The overwhelming evidence is that tiny memory allocations will always carry more overhead than operating on the data they contain. Excessive memory allocations imply small memory allocations and small memory allocations will have overhead that outweighs their contents. This actually is about as universal on modern CPUs as you can get. This is why allocating a few bytes at a time in a loop dominates performance, which all I've really been saying.

> going so far as to put false words in my mouth in order to defend your point of view. Please stop doing that.

Relax, you might learn something

Yes, it was clear that that was what you were saying, despite clear and convincing evidence that it's true in some contexts and false in others.

> For all your rabbit holes and straying off topic, it's pretty clear you know a lot more about this than chriseaton.

chrisseaton knows more about this topic than I ever will. You, by contrast, evidently don't know enough about it to understand why the things we were bringing up were relevant, miscategorizing them as "rabbit holes and straying off topic".

> Ruby runs 50x to 100x slower than native software, let alone well optimized native software. It is not a context that makes sense when talking about absolute performance.

As anyone who follows the links provided can see, some performance-critical benchmark libraries built with chrisseaton's TruffleRuby run about 1.1× slower than alternatives written in native C, although performance on larger programs is, so far, less impressive. Even the mainstream Ruby implementation MRI is typically only about 30× slower. It's true that ten years ago Ruby had performance overhead of 50× to 100×.

> Relax, you might learn something

Oh, I've learned a lot from this thread. But it wasn't by reading the GPT-2-generated Eliza-bot rants posted under the name "CyberDildonics" with no understanding of the issues; it was by reading chrisseaton's dissertation, writing and running microbenchmarks, and carefully disassembling compiler output.

You said, "If you allocate a a few bytes at a time, it will top out in the ballpark of 10 million per second per core." In my link above, I demonstrated a one-line program which, allocating a few bytes at a time, tops out at 150 million allocations per second per core; if the memory stays in use long enough to survive a minor GC, that drops to 100 million allocations per second per core. It's using the same allocator SBCL uses for everything (except large blocks), and these performance numbers include the time for deallocation. It takes into account all of the things that make memory allocation problematic for performance.† But it does an order of magnitude more allocations per second than you're saying is possible. If you were interested in whether the things you were saying were true or not, you would have tested these claims yourself instead of continuing to post bullshit; SBCL is free software, so they are easy to test.

Even LuaJIT 2.0.5 on this same laptop manages 43 ns per allocation, 23 million per second:

    function nlist(n)
        local rv = nil
        for i = 1, n do
            rv = {i, rv}
        end
        return rv
    end

    function mnlist(m, n)
        print('m='..m..' n='..n)
        for i = 1, m do nlist(n) end
    end

    mnlist(500000, 2000)

    let rec nlist n = if n = 0 then [] else n::nlist (n-1)
    let rec mnlist m n = if m = 0 then [] else (ignore (nlist n); mnlist (m-1) n)
    let m = 2000*1000 and n = 500 ;;

    print_endline ("m=" ^ (string_of_int m) ^ " n=" ^ (string_of_int n)) ;
    mnlist m n

       0x0000000000403530 <+0>:     sub    $0x8,%rsp
       0x0000000000403534 <+4>:     cmp    $0x1,%rax
       0x0000000000403538 <+8>:     jne    0x403548 <camlTimealloc__nlist_1030+24>
       0x000000000040353a <+10>:    mov    $0x1,%rax
       0x0000000000403541 <+17>:    add    $0x8,%rsp
       0x0000000000403545 <+21>:    retq   
       0x0000000000403546 <+22>:    xchg   %ax,%ax
       0x0000000000403548 <+24>:    mov    %rax,(%rsp)
       0x000000000040354c <+28>:    add    $0xfffffffffffffffe,%rax
       0x0000000000403550 <+32>:    callq  0x403530 <camlTimealloc__nlist_1030>
    => 0x0000000000403555 <+37>:    mov    %rax,%rdi
       0x0000000000403558 <+40>:    sub    $0x18,%r15
       0x000000000040355c <+44>:    mov    0x2177fd(%rip),%rax        # 0x61ad60
       0x0000000000403563 <+51>:    cmp    (%rax),%r15
       0x0000000000403566 <+54>:    jb     0x403584 <camlTimealloc__nlist_1030+84>
       0x0000000000403568 <+56>:    lea    0x8(%r15),%rax
       0x000000000040356c <+60>:    movq   $0x800,-0x8(%rax)
       0x0000000000403574 <+68>:    mov    (%rsp),%rbx
       0x0000000000403578 <+72>:    mov    %rbx,(%rax)
       0x000000000040357b <+75>:    mov    %rdi,0x8(%rax)
       0x000000000040357f <+79>:    add    $0x8,%rsp
       0x0000000000403583 <+83>:    retq   
       0x0000000000403584 <+84>:    callq  0x411898 <caml_call_gc>
       0x0000000000403589 <+89>:    jmp    0x403558 <camlTimealloc__nlist_1030+40>

       0x0000000000403558 <+40>:    sub    $0x18,%r15
       0x000000000040355c <+44>:    mov    0x2177fd(%rip),%rax        # 0x61ad60
       0x0000000000403563 <+51>:    cmp    (%rax),%r15
       0x0000000000403566 <+54>:    jb     0x403584 <camlTimealloc__nlist_1030+84>
       0x0000000000403568 <+56>:    lea    0x8(%r15),%rax

It's also true that, as you say, "memory allocation is often huge low hanging fruit for optimization." You aren't going to get this kind of performance out of HotSpot or a malloc implementation, not even mimalloc. So if you're using one of those systems, memory allocation is an order of magnitude more expensive. And, if you're concerned about worst-case performance—latency, rather than throughput, as HFT people and AAA game programmers are—probably no kind of garbage collection is a good idea, and you may even need to avoid allocation altogether, although recent versions of HotSpot make some remarkable claims about worst-case latency, claims which may be true for all I know.

Of course, even when it comes to throughput, there is no free lunch. An allocator design so heavily optimized for fast allocation necessarily makes mutation more expensive—SBCL notoriously uses segfaults for its write barrier so that writes into the nursery are as fast as possible, a cost that would be intolerable for more mutation-oriented languages like Java or C++; and heavy mutation is generally a necessary evil if latency is important. (Also, I think there are algorithms, especially in numerical computation, where the best known mutation-based algorithms have a logarithmic speedup over the best known pure functional algorithms.)

You can find a more detailed discussion of some of the issues in https://archive.fo/itW87 (Martin Cracauer's comparison of implementing memory allocation in LLVM and SBCL, including years of experience running SBCL in production and extensive discussion of the latency–throughput tradeoff I touch on above) and the mimalloc technical report, https://www.microsoft.com/en-us/research/publication/mimallo.... The mimalloc report, among other things explains how they found that, for mimalloc, BBN-LISP-style per-page free-lists (Bobrow & Murphy 1966, AD647601, AFCRL-66-774) were faster than pointer-bumping allocation!

______

† This build of SBCL does have multithreading enabled, and the allocation benchmark takes the same amount of time running in a separate thread, but on my machine it doesn't get a very good speedup if run in multiple threads, presumably due to some kind of allocator contention. (I know that SBCL's GC has to stop all mutator threads during a collection, but the original allocation benchmark here only spends 5% of its time in the GC, so this isn't enough to explain the observed multithreading slowdown, where one thread takes 6.5 ns per allocation, while two threads each take 9.2, three take 17, and four take 29, so although this is a 4-core CPU, at that point multithreading is imposing a slowdown rather than providing a speedup. I suspect that this version of SBCL isn't providing a per-thread nursery the way modern VMs do, so allocation-heavy code like this gets serialized.)

I wrote a XML DOM parser that relied heavily on placement new and could recycle most of the nodes among documents. It sped up parsing by over 20 times. Some documents (> 5 MB) that were previously unparseable became parseable.

If there's nothing there then malloc the rounded size plus my header, fill out my header (linked list fields plus block nominal size plus signature) and return a pointer to the data portion.

On a free/delete, look backwards from the given pointer for a signature. If its not there, just free it with the library. If its there, look in the hash table by the nominal size and link this block there.

That's it! You can protect the hash table and linked lists with a critical section if you want to be multi-threaded. Optional features include a table of block counts for diagnostic purposes. Maybe an assert on the number of blocks, to catch runaway allocation.

All that is a page or two of code.

https://github.com/codr7/libcodr7/blob/master/source/codr7/l...

https://en.wikipedia.org/wiki/Persistent_data_structure