Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast linked lists

dygalo.dev

Post reply on HN
Print view View original

21–30 of 131 posts

Re: Fast linked lists

#21

Post by Someone »

wavemode wrote: post #16
bjoli wrote: post #10

Earlier quoted context omitted.

Most languages with linked lists as an important part (lisps mostly) all have well optimized linked lists that end up with a lot better memory locality.

How does that work? I don't follow how any runtime or compile-time optimization can solve the problem of locality for a linked list. If the data wasn't allocated sequentially, then it's simply not going to be sequential (unless you move it).

A sufficiently smart compiler can detect that a new node gets allocated and then appended to a list, and allocate the node near the other nodes of that list.

To have a good chance that there is space near the other nodes, you’d have to reserve memory up front for each list you’d want to do that with, though, and that will kill cache locality before that optimization sets in. Corrections welcome, but I don’t see that (easily) being a net win. But hey, with a sufficiently smart compiler at hand, you can do wonders. (Edit: when looking at pure functions, it many times may not be that hard to discriminate between “this allocation will be returned” and “this allocation is temporary”. For example, if you use map to apply a function to all elements in a list, and that function is pure, detecting that only the return values of that function will be visible after the function returns isn’t that hard)

An easier win is that lisp garbage collectors tend to move memory, and thus can try to move nodes that reference each other close together. You get that for free with a semispace collector, but that has quite a few disadvantages, so you don’t want to use that. A generational collector also will do it a bit, though (say you create a few million nodes of garbage to build a list of a few hundred results. Then, after generational collection, those few hundred cells will be closer together than before)

Re: Fast linked lists

#22

Post by s17n »

hayley-patton wrote: post #17
wavemode wrote: post #16

Earlier quoted context omitted.

How does that work? I don't follow how any runtime or compile-time optimization can solve the problem of locality for a linked list. If the data wasn't allocated sequentially, then it's simply not going to be sequential (unless you move it).

SBCL tries its hardest to allocate sequentially, then moves lists to be sequential in GC.

The entire theoretical advantage of linked lists over vectors (constant time insertion and deletion) comes from not sequentially allocating them.

Re: Fast linked lists

#23

Post by Xeamek »

kolbe wrote: post #7

Linked list benchmarks are amazing.... if you don't thrash your cache on inserts so all its elements are contiguous. You get all the benefits of a vector and a linked list, without the reality that linked lists mostly don't get populated 100% consecutively, and thus can be anywhere in memory.

Why cant we 'simply' get processor extension to mark data as pointer so that the prefetcher would actually know what to fetch.

From my understanding this is what led to the recent 'unpatchable' exploit in Apple's M1, but rather then trying to guess it by some heuristic, why not just give compilers option to make that optimization?

Re: Fast linked lists

#24

Post by EGreg »

duped wrote: post #14

It strikes me the bottleneck for this problem isn't Vec or List, it's the serde_json Value type that needs to be used. This is useful for serializing/deserializing values into Rust types but if you're trying to validate JSON against a schema you don't actually need the JSON value data, just the types of the nodes (or more specifically, you only need some of the value data, and probably not much of it, so don't pay fo…

Just use capn’proto. No deserialization needed !

Re: Fast linked lists

#25

Post by screcth »

s17n wrote: post #22
hayley-patton wrote: post #17

Earlier quoted context omitted.

SBCL tries its hardest to allocate sequentially, then moves lists to be sequential in GC.

The entire theoretical advantage of linked lists over vectors (constant time insertion and deletion) comes from not sequentially allocating them.

If you have a compacting GC you are going to move the nodes anyway, so why not reallocate them sequentially?

Re: Fast linked lists

#26

Post by aabhay »

EGreg wrote: post #24
duped wrote: post #14

It strikes me the bottleneck for this problem isn't Vec or List, it's the serde_json Value type that needs to be used. This is useful for serializing/deserializing values into Rust types but if you're trying to validate JSON against a schema you don't actually need the JSON value data, just the types of the nodes (or more specifically, you only need some of the value data, and probably not much of it, so don't pay fo…

Just use capn’proto. No deserialization needed !

Whats your experience like using it? Is it ergonomic or does it require you to do lots of type gymnastics?

Re: Fast linked lists

#27

Post by infamouscow »

Xeamek wrote: post #23
kolbe wrote: post #7

Linked list benchmarks are amazing.... if you don't thrash your cache on inserts so all its elements are contiguous. You get all the benefits of a vector and a linked list, without the reality that linked lists mostly don't get populated 100% consecutively, and thus can be anywhere in memory.

Why cant we 'simply' get processor extension to mark data as pointer so that the prefetcher would actually know what to fetch. From my understanding this is what led to the recent 'unpatchable' exploit in Apple's M1, but rather then trying to guess it by some heuristic, why not just give compilers option to make that optimization?

This was the idea of Itanium. It failed mostly because of economics.

It turns out programmers, or rather their employers, don't really care about using hardware efficiency. They care about shipping things yesterday, because that's how business deals get closed, and making software efficient is secondary to money changing hands. Performance never really matters to business people after the checks are cashed.

Multicore computers have been ubiquitous for more than a decade, yet the overwhelming majority of software built today is single-threaded microservices, where in they spend most of their time serializing and deserializing message payloads.

This is all really to say that most performance is already being left on the table for the majority of what computers are used for today.

Re: Fast linked lists

#29

Post by Xeamek »

infamouscow wrote: post #27
Xeamek wrote: post #23

Earlier quoted context omitted.

Why cant we 'simply' get processor extension to mark data as pointer so that the prefetcher would actually know what to fetch. From my understanding this is what led to the recent 'unpatchable' exploit in Apple's M1, but rather then trying to guess it by some heuristic, why not just give compilers option to make that optimization?

This was the idea of Itanium. It failed mostly because of economics. It turns out programmers, or rather their employers, don't really care about using hardware efficiency. They care about shipping things yesterday, because that's how business deals get closed, and making software efficient is secondary to money changing hands. Performance never really matters to business people after the checks are cashed. Multicore…

I mean sure, I don't doubt 99% of end-user programmers wouldn't look twice at something like this, but compilers designers probably would care.

And it's not like the companies arent trying this idea (again, M1 exploit). But for whatever reason they want to keep cpus as black box, perfect abstract machines, even though we know they aren't

Re: Fast linked lists

#30

Post by cogman10 »

kevingadd wrote: post #5

I was hoping to see optimization of the actual linked list manipulation and traversal (pipelining? i'm not sure what you'd do), but this is still a neat post. It's cool to see thought put into various parts of the problem, like reallocation/preallocation, stack allocation, etc.

reallocation/preallocation actually does increase manipulation and traversal performance.

The major slowness of linked lists is cache inconsistency. New nodes can be put all over the memory space. However, if you can make sure all or part of the list exists in contiguous blocks of memory, then there's a good chance that when the CPU loads up the next node it will also grab the next 3 nodes in a cache line.

The closer these node addresses are in memory, the faster things will be.

Post reply on HN