[HN Gopher] Drop millions of allocations by using a linked list ...
___________________________________________________________________
Drop millions of allocations by using a linked list (2015)
Author : ddtaylor
Score : 167 points
Date : 2021-03-12 09:09 UTC (13 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| Chirono wrote:
| Except it turns out to be "drop millions of allocations by
| changing an exponential recursive algorithm to a linear scan that
| does a different (and incorrect) thing". So it seems like the
| linked list part of it was incidental.
| cygx wrote:
| The exponential version was also broken, just in a different
| way (cf https://github.com/rubygems/rubygems/pull/1191#issuecom
| ment-...).
| rsp1984 wrote:
| Lessons from high-performance / embedded development: If you know
| the size of your data beforehand, or can at least put a bound on
| it, it's best to pre-allocate your memory and then hand out bits
| as needed through a custom allocator working on the pre-allocated
| set. That way you have only a single allocation and all your data
| is contiguous in memory (huge deal for cache coherency and
| therefore speed of access). Very easy to put a vector/ArrayList
| -type interface on top of this.
|
| 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.
| simiones wrote:
| Most GC languages use bump-pointer allocation and/or compacting
| garbage collection to (try to) ensure that objects are stored
| in memory in this way regardless of being dynamically
| allocated.
|
| 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)
| gameswithgo wrote:
| I've seen a Linked List get allocated very contiguously at
| times in .NET when it is just a toy program, like just
| benchmarking linkedlist performance, it sometimes does really
| well. But in the context of a big running program with other
| things in the heap it is much less likely to work out so
| well.
| pradn wrote:
| Modern memory allocators like tcmalloc are pretty good with
| putting structs of the same size in contiguous areas of the
| heap. For smaller structs (which most real world cases fall
| under), it's just one lookup to find the next place to put
| the new object. So, C and Java will have similar performance
| for allocating a lot of small objects, I think. There's
| probably a difference on the deallocation side, especially
| with fragmentation, but I'm not as knowledgeable about that.
| If someone has a richer explanation, I'd love to hear.
| scott_s wrote:
| As someone who worked on memory allocators in a past life:
| cosign. Size-class based allocation for small objects is
| how modern memory allocators have worked for a long time
| now. I'm genuinely baffled by how many people think that
| the bump-pointer allocation for same-sized objects is
| unique to garbage collection.
| pradn wrote:
| Thanks for confirming this. Do you have an idea of how
| modern allocators compare with generational GCs on the
| cleanup / realloc / fragmentation side?
| kazinator wrote:
| Even if you have a bump allocator, the fact is that a linked
| list requires storage for the pointers, which are not needed
| in an array. That makes the list bigger, and bigger means
| worse from a caching point of view. Fewer parts of a linked
| list fit into a cache line and so on.
|
| 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.
| galangalalgol wrote:
| And if your data is truly contiguous and its struct of
| arrays instead of the other way around, SIMD becomes much
| more usable.
| simiones wrote:
| Absolutely, I'm not claiming linked lists are "better" than
| arrays. The GP was mentioning memory fragmentation and
| cache behavior, and I was pointing out that GCs can, at
| least in some conditions, make linked lists more efficient
| then they are in C (comparing naive implementations).
|
| But yes, linked lists are almost always worse than arrays,
| unless you're doing huge amounts of add/remove on large
| amounts of data.
| hinkley wrote:
| In most GCs the mark phase also disrupts the cache by doing
| what looks a lot like a table scan. That's one of the reasons
| for generational collectors. Better cache locality.
| junippor wrote:
| In Julia if you have an estimate of the size (not necessarily a
| hard bound) you can `sizehint!` to reduce the number of
| allocations.
| ciarcode wrote:
| I think this is the solution used in FreeRTOS if you use heap1
| as allocator.
| BunsanSpace wrote:
| the SOP with C++ is you overload the new and delete operators
| and implement your own heap.
|
| 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.
| brundolf wrote:
| You're talking about arenas, right?
| https://en.wikipedia.org/wiki/Region-based_memory_management
| pdpi wrote:
| I think the term you're looking for is cache locality. Cache
| coherence is about ensuring that caches local to different
| cores see the same values for any one given chunk of memory.
| gpderetta wrote:
| It seems to be a very common mistake. Understandable as they
| are somewhat related as bad cache locality can cause unneeded
| coherency protocol traffic.
|
| Of course locality is important even on single core cpus with
| no need for coherency.
| matheusmoreira wrote:
| Why can't we have this as a general interface in standard
| libraries? For example, we could have a contextual allocation
| function: // Contiguous array of 1024 objects
| of type context = contextual_allocation(1024, sizeof
| type); // obtain pointer to next free object
| object = allocate(context);
| kristoff_it wrote:
| For an overview of how Zig does this and at the same time a
| nice overview on different types of allocators:
|
| What's a Memory Allocator Anyway? by Benjamin Feng
|
| https://www.youtube.com/watch?v=vHWiDx_l4V0
| latch wrote:
| I believe this is how Zig works. Specifically the
| FixedBufferAllocator. It can further be paired with the
| ArenaAllocator to make management dead simple.
| vbarrielle wrote:
| Zig requires the allocator to be specified for each
| allocation: https://ziglang.org/documentation/0.5.0/#Memory
|
| 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).
| thechao wrote:
| In the mid 00s, my advisor had me explore the concept of
| adding default parameters to C++ functions where the
| default snagged the nearest lexically scoped named object
| of the right type from the calling environment, i.e.,
| int someFunctionThatAllocates(int A, int B, allocator
| const& alloc = default);
|
| Then in the calling environments: {
| 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 { } }
|
| It handily solves a number of problems. In particular, we
| were looking at how we manage heap allocation for large
| sparse matrix libraries a la MTL4.
| gpderetta wrote:
| Interesting. Isn't this this vaguely reminiscent of
| implicits in Scala?
| injidup wrote:
| It's called implicits in Scala
| fanf2 wrote:
| The obstack api in glibc is exactly this https://www.gnu.org/
| software/libc/manual/html_node/Obstacks....
| alexhutcheson wrote:
| This is called arena allocation, and there are many
| implementations of the concept.
|
| 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: htt
| ps://github.com/electronicarts/EASTL/blob/master/include/...
| sgtnoodle wrote:
| I'd describe it more as a pool or block allocator.
|
| 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.
| mytailorisrich wrote:
| > _it 's best to pre-allocate your memory and then hand out
| bits as needed through a custom allocator working on the pre-
| allocated set._
|
| 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.
| kqr wrote:
| Doesn't even malloc do this under the hood by only occasionally
| calling sbrk and otherwise handing out blocks from an
| internally managed contiguous region?
|
| What's the point of doing this again, manually? Or am I
| mistaken in my memory of the common modern malloc
| implementations?
| sly010 wrote:
| What's the point of buying a jeep wrangler (or a ferrari),
| when you already have a subaru? Don't they all have 4 wheels?
|
| 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
| scott_s wrote:
| Often, yes, you're better off just using the general purpose
| memory allocator.
|
| 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.
| -\\_(tsu)_/-
| JoeAltmaier wrote:
| It can be an order of magnitude faster to do it yourself,
| depending on how balled up the runtime library has gotten. If
| you can make some simple guarantees like "I'll realloc
| similar sized blocks mostly" and "I'm single-threaded thru
| these calls" then you can drop the bulk of the runtime drama.
| cnity wrote:
| malloc aligns very conservatively (because it doesn't know
| the size of the data you're allocating for), so there are
| some space gains to be had there.
|
| 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...
| CyberDildonics wrote:
| That doesn't contain calls to sbrk at all, it maps memory
| in with mmap which is typical of every modern memory
| allocator.
| cnity wrote:
| You're right, I misinterpreted the calls to __brk
| quantumofalpha wrote:
| It uses both brk/sbrk ("__brk()" in that code) and mmap,
| the latter for allocating larger bits of memory. GNU libc
| does the same thing from what I remember from straces.
| as-j wrote:
| > Lessons from embedded development
|
| 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.
| sgtnoodle wrote:
| I usually end up with a singly linked list when implementing
| a singleton API that needs to support an arbitrary number of
| application created objects. Rather than have the singleton
| pre-allocate the memory, the application has to do it, then
| pass it into the API to use for the lifetime of the program.
| The various parts of the application knows how many objects
| it needs, and can statically allocate just the right amount
| of memory.
| dragontamer wrote:
| On the contrary: small objects mean that fragmentation is NOT a
| problem: because your small nodes can be "fit anywhere".
| Furthermore, if you've got 1000x 8-sized allocations, any of
| those "holes" can be repurposed for other 8-sized allocations.
|
| 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.
| ameixaseca wrote:
| Everything you mentioned can be done with statically
| allocated arrays - if you have known bounds - or lists of
| large arrays, as mentioned before.
|
| 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.
| dragontamer wrote:
| > Lists will eventually become a problem since your
| next/prev pointers may not be pointing to adjacent memory
| positions
|
| 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];
| }
|
| Now we have the spatial locality you so desire, while still
| retaining the ability to rearrange the list. In fact,
| add/remove is still possible (though the malloc/free is
| harder to keep track of: if you're in a Dancing-links
| scenario, you may not ever need to call free)
| ameixaseca wrote:
| I mentioned 3 points, you addressed one for a very
| specific scenario. In any case, even if you say your list
| has adjacent elements, the other two points still apply.
|
| 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.
| dragontamer wrote:
| I can address the other point too.
|
| > 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.
| Twisol wrote:
| Perhaps naively, would a struct-of-arrays perform better
| than an array-of-structs? I imagine that the separate
| `next` and `data` arrays might be packed better, and
| instead of processing one cache line at a time, you could
| load two cache lines simultaneously to process double the
| sequential data with every round-trip to RAM.
|
| 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.
| alexhutcheson wrote:
| But then your objects are scattered all over the address
| space, which means that objects you're accessing in sequence
| are unlikely to be in the same cache line, so you pay a cache
| miss on every single access.
|
| 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
| dragontamer wrote:
| But the entire point of linked lists is to insert in the
| middle in constant time.
|
| 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.
| penetraitor69 wrote:
| My understanding is that push/pop from the front/back of
| linked lists are constant time, but that inserts in the
| middle necessitate looping through the linked list until
| you get to the correct index, which is a O(n) operation.
| dragontamer wrote:
| > but that inserts in the middle necessitate looping
| through the linked list until you get to the correct
| index, which is a O(n) operation.
|
| 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
| penetraitor69 wrote:
| Oh, gotcha; I just meant in the general case.
| gameswithgo wrote:
| Yes, but if you actually measure some scenarios, it is
| usually overall faster to pay the cost of O(1) copy. This
| of course depends on how often you insert things into the
| middle, vs how often you iterate over the collection. But
| on a modern computer it is surprising how big that ratio
| needs to be! In Knuths prime this tradeoff didn't really
| exist, because memory accesses were about at the same
| speed as executing an instruction, rather than ~200 times
| slower.
| dragontamer wrote:
| Knuth's Dancing Links is originally from 2001, and was
| first published to book form in Fasicle 6 (2019).
|
| 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.
| jasode wrote:
| _> , you need a O(1) memcpy_
|
| 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.
| dragontamer wrote:
| Ah jeez. That's what I get for typing fast.
|
| 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.
| eniotna wrote:
| In most real world problems, you don't really care about
| keeping a data structure sorted at all time. All you
| want, is to have it sorted when you're about to do X. So
| it's generally faster to just have a contiguous chunk,
| insert at the end, then sort when you need.
| dragontamer wrote:
| And ironically, that's when we get into fragmentation
| issues for arrays!
|
| 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.
| gpderetta wrote:
| MSVC STL uses the golden ratio instead of doubling for
| std::vector allocation which means that you can reuse
| contiguous runs of previously deallocated chunks to
| fulfill future allocations, while still meeting the
| standard asymptotic O(1) bound on push_back.
|
| 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.
| alexhutcheson wrote:
| What environment are you working in where this is a
| problem in practice?
|
| 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.
| dragontamer wrote:
| I've been experimenting with data-structures on GPUs.
| 8GBs of RAM to share across 4096 SIMD-cores (well... 64
| "compute units" with 64-way SIMD... you know...). But
| Vega64 runs 4-threads per SIMD-core, so you actually need
| 16384-SIMD threads before you utilize the processor. (And
| at occupancy 10, you have 10-threads per hardware thread,
| or 163840 SIMD-threads total)
|
| 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...
| alexhutcheson wrote:
| Not sure what GPU algorithms you're trying to implement,
| but linked lists (and generally anything with pointer-
| chasing) are almost maximally terrible on GPUs - they are
| really not designed for that.
| dragontamer wrote:
| > (and generally anything with pointer-chasing)
|
| 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.
| alexhutcheson wrote:
| Naive tree traversal on a GPU actually has pretty bad
| performance, due to execution divergence. It takes a lot
| of application-specific reframing of the problem to
| making working with BVH trees efficient:
| https://developer.nvidia.com/blog/thinking-parallel-part-
| ii-...
| dragontamer wrote:
| Its not as complicated as it sounds. Stream compaction
| solves execution divergence. The end. Instead of
| recursively searching the tree, you select the members of
| the tree with a child.
|
| No, you can't do naive 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).
| CyberDildonics wrote:
| This is extremely poor advice in practice.
|
| 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.
| alexhutcheson wrote:
| Sorted linked lists are also especially-not-useful,
| because you can't binary search them, which is often the
| main benefit to having something sorted.
|
| 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.
| dragontamer wrote:
| > 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)
| alexhutcheson wrote:
| > 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).
|
| 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
| dragontamer wrote:
| Gap buffer is very good.
|
| > 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.
| captain_price7 wrote:
| I think for C++ vector, when current underlying array gets
| filled, the common strategy is allocate a new array double the
| size of the current one, and copy contents over to that.
| tester34 wrote:
| same in C# for list
| rerx wrote:
| But if you expect an upper bound of the required size of that
| stay, it may be worthwhile to explicitly set the capacity of
| the vector to avoid these reallocations.
| spacechild1 wrote:
| That's exactly the purpose of std::vector's "reserve"
| method, btw.
| twoodfin wrote:
| I once worked with a C++ text processing library that saw
| more than a 50% throughput bump just from reserve()'ing
| std::string and std::vector space in hot code paths.
| jedimastert wrote:
| I remember seeing a sizable astrophysics Fortran program from
| many decades prior that had one "MEMORY" array declared at the
| beginning of the program and legit used it for every single
| byte of memory for the entire program. It was _nuts_
| vecter wrote:
| The same goes for the AMBER computational chemistry FORTRAN
| program. The array is called X.
| jedimastert wrote:
| Actually, that might be what I'm thinking of. For some
| strange reason (this was in 2013, mind you) I was involved
| with translating legacy Fortran projects for multiple
| departments.
| queuebert wrote:
| TEKTON, a crater modeling code, had this, but I think it
| called the array 'a'.
| eru wrote:
| Seems like an example of a persistent data structure to avoid
| copying?
|
| https://en.wikipedia.org/wiki/Persistent_data_structure
| naranha wrote:
| Unrelated to the article, but perhaps an interesting fact: as a
| Java programmer you perhaps know that using the class
| java.util.LinkedList is almost always worse in than using plain
| arrays or ArrayList. Even though there are much less allocations,
| the overhead for maintaining the linked list data structures is
| immense. And it turns out that computers are pretty fast at
| allocating memory.
|
| But there more optimized implementations of linked lists of
| course (probably using arrays as well internally (?)).
| exDM69 wrote:
| Yes, linked lists have terrible cache behavior and usually the
| performance of any packed structure with less pointer chasing
| should beat it. ArrayList, Vector, whatever you call it usually
| is faster.
|
| 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.
| cmeacham98 wrote:
| > 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.
|
| 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.
| exDM69 wrote:
| You don't need to couple the linked list nodes with your
| allocations. Either you make an array of link structs or
| embed your links in the stored struct (intrusive linked
| list).
|
| 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.
| cmeacham98 wrote:
| You still need to allocate a node for each addition to
| the LL for the stored struct, unless you pre-allocate a
| set of them, and at that point you very likely are better
| off using a static array.
|
| 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.
| gsg wrote:
| You can easily see by searching for 'kmalloc' (or
| 'malloc') at https://github.com/torvalds/linux/blob/maste
| r/include/linux/... that it does no such thing.
|
| 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); }
|
| No allocation, just mutating some fields in preexisting
| list_head structures. Those are by convention stored as a
| field in whatever struct needs to be kept in the list,
| which is what 'intrusive' means.
| cmeacham98 wrote:
| And where do you think that "new" comes from? I guess my
| phrasing is poor so I should have been clearer: elements
| in kernel LLs generally came from a kmalloc, even though
| the LL functions don't use a malloc themselves.
| exDM69 wrote:
| Yes, preallocation was what I was referring to. The other
| strategy is what Linux does, embedding the links to the
| stored struct.
|
| Static arrays are poor at joining, splitting, removal and
| merging.
| cmeacham98 wrote:
| > Static arrays are poor at joining, splitting, removal
| and merging.
|
| 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".
| MauranKilom wrote:
| Merging (in the sense of retaining some order property)
| is probably just as fast in static arrays as in lists.
| For large element sizes, you'd use an array of pointers
| (requiring only one pointer per element in the data,
| doubling during the merge) and the pointer fiddling
| during the merge is about the same for either. For small
| elements, the list overhead alone is probably enough to
| make arrays faster.
|
| O(1) joining, splitting and removal are of course not
| beatable by contiguous data structures.
| mypalmike wrote:
| LLs are often used to manage fixed sized object pools. So
| yes, statically sized arrays, but with pointers between the
| elements acting as linked lists.
| pdpi wrote:
| > Intrusive linked lists drop one extra pointer chase.
|
| 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.
| DSMan195276 wrote:
| I think your typical template-based list is actually a bad
| example :P Maybe there's something about C++ I don't know,
| but typically those implementations only allow for adding
| one list node (via the template wrapping), and also they
| can't usually take an element from one list and then attach
| it to another one. Where-as intrusive implementations like
| the Linux Kernel's allow for any number of list nodes or
| other data structures to be placed alongside the data, and
| the elements can be moved onto any list you want without
| any allocations necessary.
| gpderetta wrote:
| std::list has splice to move nodes between lists.
|
| 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.
| DSMan195276 wrote:
| Once you do that though (use a "true" intrusive
| implementation), you typically lose the "keep the list
| structure out of your data" aspect. std::list allows you
| to avoid that, but carries its own limitations that
| embedding the list structures into the data does not.
|
| 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.
| skohan wrote:
| > it turns out that computers are pretty fast at allocating
| memory
|
| 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
| chrisseaton wrote:
| What do you think an allocation involves in a modern language
| implementation?
|
| 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!
| MauranKilom wrote:
| If you don't use a per-thread heap, then you won't get
| around synchronizing different threads for allocation. If
| that necessarily serial part of your code makes up even 1%
| of the time your program needs (before parallelization),
| then going from 100 threads to 1000 threads will only be a
| speedup of 81% (whereas you'd ideally expect 900%). That's
| not good for HPC.
|
| See https://en.wikipedia.org/wiki/Amdahl%27s_law.
| chrisseaton wrote:
| > If you don't use a per-thread heap
|
| Well why wouldn't you?
|
| > See https://en.wikipedia.org/wiki/Amdahl%27s_law
|
| Allocation should be embarrassingly parallel in the fast
| path.
| CyberDildonics wrote:
| There is a lot of truth to this and you are one of the
| few people I've seen mention amdahl's law in the correct
| context.
|
| There are multiple malloc implementations (gcc and maybe
| clang) that are supposedly multi-threaded now and
| multiple allocators are explicitly made for it like
| jemalloc, so I don't think the situation is quite as dire
| anymore.
|
| That being said, I agree that using per-thread heaps is a
| much better structure by default for a heavily multi-
| threaded program since allocations crossing threads
| probably should be handled explicitly and memory mapping
| from the OS will still block (as far as I know).
| [deleted]
| joosters wrote:
| That's the absolute best case for the simplest malloc
| implementation possible.
|
| 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.
| kragen wrote:
| This is correct. Here is a Lisp function that allocates N
| cons cells: $ 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
|
| Let's see how long it takes to allocate two million
| 500-item lists, totaling a billion allocations:
| * (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
|
| That's 6.5 nanoseconds and 18 "processor cycles" (does SBCL
| use performance counters for this or is it guessing?) per
| 16-byte allocation. That's about 150 million allocations
| per second, including the time to initialize those
| allocations and increment the loop counter and whatnot, and
| also (contra chrisseaton) the time to deallocate those
| lists. If we increase the list length and proportionally
| decrease the iteration count, this performance remains
| consistent up to 50,000-item lists, but at 2000 iterations
| of half a million items, it starts taking 10 seconds
| instead, presumably because the lists no longer fit into
| the generational garbage collector's nursery, so it has to
| spend a third of its time in the garbage collector.
|
| 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
|
| As best I've been able to figure out, the nursery
| allocation pointer is stored in memory at [R12+24], the
| pointer to the freshly allocated dotted pair comes out of
| this sequence (at L4) in RCX, and the pointer to the end of
| the nursery is stored in memory at [R12+32]. So the actual
| allocation is, in the normal case, the six instructions
| from 029ECEF9 up to 029ECF16. If the nursery is full, it
| takes the jump to L9 to invoke a minor garbage collection.
| It may help to know that on amd64 SBCL represents dotted-
| pair pointers with, essentially, a pointer to their 7th
| byte, which is what all that RCX+7 nonsense is about.
|
| 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!)
| CyberDildonics wrote:
| That is very wrong. If you allocate a a few bytes at a
| time, it will top out in the ballpark of 10 million per
| second per core, which is still 300 cycles at 3ghz.
|
| 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.
| gsg wrote:
| chrisseaton is talking about the bump-pointer allocator
| in a modern GC, not an implementation of malloc/free. The
| performance characteristics are quite different.
|
| 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.
| CyberDildonics wrote:
| There are no situations where it makes sense to say that
| lots of allocations are cheap and only cost a few
| instructions.
|
| 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.
| kragen wrote:
| > _There are no situations where it makes sense to say
| that lots of allocations are cheap and only cost a few
| instructions._
|
| 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.
| CyberDildonics wrote:
| What you are talking about is the equivalent of adding 1
| to the size of a C++ vector with a large capacity on each
| iteration of a loop.
|
| 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.
| ansible wrote:
| It is worth remembering that linked lists were invented back in
| the dawn of computing.
|
| 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.
| gpderetta wrote:
| most importantly, those machines were not fully pipelined (if
| at all) and certainly not capable of out of order execution,
| so the inherent forced serialization of a linked list
| traversal was not an issue.
| mcculley wrote:
| It is worse in Java. The standard LinkedList class in Java
| stores references to the data, not the data, in nodes, so
| there is more pointer chasing.
| pjmlp wrote:
| For the time being, value types will eventually fix that.
|
| Ironically some of the ideas how to proceed with value
| types integration were already present in Eiffel, but so
| are design decisions.
| sltkr wrote:
| This applies equally to ArrayList.
| mcculley wrote:
| Yes, but if you can use ArrayList, you can also use an
| array. If you want to be able to remove an object from
| the middle without moving objects around, you have no
| choice other than LinkedList and the extra references.
| xirbeosbwo1234 wrote:
| So do arrays. You can never have an "inline" object. It's
| always a reference.
|
| Java has another problem because each node is an object,
| though. Every object has (I believe) about 16 bytes of
| overhead. That will double the size of each node.
| twic wrote:
| There is such a thing as an unrolled linked list, which is a
| bit like a flat B-tree:
|
| 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.
| creata wrote:
| I wonder whether someone's invented a way to take a nice ADT
| like data List a = Cons a (List a) | Nil
|
| and automatically unroll it to fill at least a cache line.
| That sounds like it'd be a small win for performance, but I
| don't know.
| gsg wrote:
| Yes, this has been done a few times. CDR-coding was a
| hardware-assisted method of unrolling a Lisp list
| (complicated somewhat by the need to support mutation of
| car and cdr) that appeared on Lisp machines, and there's a
| Appel/Reppy/Shao paper on unrolling linked lists in the
| context of Standard ML.
|
| There's also some interesting work on flattened versions of
| arbitrary tree structures:
| https://engineering.purdue.edu/~milind/docs/ecoop17.pdf
| winrid wrote:
| This was actually the correct answer to "build a linked list"
| interview question I did.
|
| They didn't explicitly ask for it to be unrolled, just
| sounded frustrated that I didn't make a fancy unrolled one.
| :)
| karmakaze wrote:
| In Java arrays or ArrayList usually mean 'of references' so
| don't get the full cache locality benefit until Valhalla ever
| gets done. For primitive types, there are numerous primitive
| collection libraries that use primitive values and optionally
| object references.
| Cthulhu_ wrote:
| This is the thing with algorithms and leetcode and the like;
| I've got about ten years of professional experience, and in all
| of my career (CRUD apps, full stack; sounds boring but I've
| touched many different industries) I've NEVER had to think
| about what data structure to use.
|
| 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.
| ALittleLight wrote:
| I've been leetcoding recently and I feel like most leetcode
| problems have similar requirements to what you describe vis a
| vis data structures. I've been focusing on Medium difficulty,
| maybe it's different on hard, but I've been doing the
| occasional hard too and not noticed it. The problems mostly
| seem to be about realizing what algorithm you'll need and
| implementing it.
|
| 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.
| rottc0dd wrote:
| I am not a comp science guy, and I just know next to nothing
| in case of either data structures and algorithms. But,
| knowing how and why the data structures work can help you
| when slapping the code does not work.
|
| 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.
| w1nk wrote:
| I never enjoy seeing this line of argumentation pop up when
| we (as the computing industry) discuss practicalities of data
| structures and algorithm choices. I've got a bit over twice
| your time in the industry and one of the things that is still
| very clearly on an upward walk is the size of our N's (think
| big O) in all of our applications and across all of our data
| structures.
|
| 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.
| pjmlp wrote:
| I think it is crucial to understand data structures and
| algorithms, more so than whatever way they exposed in each
| programming language, as Nicklaus Wirth puts it, Algorithms
| + Data Structures = Programs.
|
| 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.
| bartread wrote:
| I tend to agree even though most of the time for me array
| like structures are often "enough". The thing is it's the
| 10%, the 5%, or the 1% of the time where you really see the
| benefit of using those structures.
|
| 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.
| nmfisher wrote:
| Data structures are funny, because most of the time they're
| (a) the last thing you worry about (after feature
| specification/architecture/implementation/etc), and (b) it's
| usually pretty obvious which data structures you to use (and
| which to avoid).
|
| 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.
| mypalmike wrote:
| > comprehensive knowledge of data structures won't be
| needed in 99% of the average career,
|
| How does one write software professionally without a solid
| grasp of data structures?
| nmfisher wrote:
| ...by doing what thousands of people do around the world
| every day (and what OP was referring to) - using the
| List, HashMap, Stack and Queue implementations provided
| by your language of choice.
|
| 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).
| kragen wrote:
| Yesterday and the day before I wrote this eco-logical
| simulation: http://canonical.org/~kragen/sw/dev3/qabbits
|
| 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.
| codr7 wrote:
| From my experience, the only kind of linked list that still
| sometimes makes sense is the embedded one.
|
| https://github.com/codr7/libcodr7/blob/master/source/codr7/l...
| queuebert wrote:
| On a related note, Rust's Cow (copy on write) type is great for
| managing a large area of allocated memory where many threads are
| reading and only a few threads write. You can dole out pointers
| like candy without worrying about race conditions, because the
| moment they are written to a new allocation is created and the
| pointer moved.
| JoeAltmaier wrote:
| As an embedded programmer, I often end up using a simple linked-
| list for memory allocations (when I allocate at all). But I hash
| by rounded-up blocks. Instead of having hash nodes for every
| sized block e.g. {...114, 116, 117, 118...} I'll use {64, 128,
| 256, 512...}. With 8 or nine hash buckets the app will re-use the
| same memory (after allocating a working set) forever.
| ciconia wrote:
| Can you share the algorithm?
| munificent wrote:
| Search for "small block allocator" and you'll probably find
| some good resources.
| JoeAltmaier wrote:
| I just look in a hash table by rounded block size. If there's
| something there, its a linked list of 'free' blocks; unlink
| one and return a pointer to the data portion.
|
| 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.
| inglor_cz wrote:
| Once upon a time, there was Symbian OS, with very limited
| resources and an ugly tendency to fragment the heap. And the
| heaps were small, given how little memory popular devices like
| Nokia E52 had.
|
| 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.
| elesbao wrote:
| Nice to see the Ruby folks learning some CS !
___________________________________________________________________
(page generated 2021-03-12 23:02 UTC)