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

71–80 of 131 posts

Re: Fast linked lists

#71

Post by cyberax »

_xnmw wrote: post #51
torusle wrote: post #37

> Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects. I beg to disagree. In kernels, drivers, and embedded systems they are very common.

Why? Why would someone reach for a linked list in a kernel, driver, or embedded system?

In kernels, it's usually hard to get general-purpose allocation working reliably in all contexts. And you need that for resizable vectors. With lists, you just need to be able to grab an element-sized block. Quite often, it's even done with the memory page granularity.

In addition, a lot of data structures might be shared across multiple cores. Linked lists can be traversed and mutated concurrently (although with a bit of care).

Re: Fast linked lists

#72

Post by Xeamek »

kolbe wrote: post #39
infamouscow wrote: post #27

Earlier quoted context omitted.

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…

Given how much of today's computer needs are dependent on a database query, this is no surprise. Who cares about the micros you gain with added efficiency while there's a 100ms db query return in the path?

Apparently Apple and Intel do, since they introduced those changes into their silicon

Re: Fast linked lists

#73

Post by Xeamek »

Joker_vD wrote: post #36
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?

I don't think making CPU issue (likely bogus) pre-fetches for every field in the cache line that's marked as a pointer is really that good idea. At best, you save couple of cycles because the fetches are started a one or two instructions earlier before the actual load instruction for "loading the linked pointer" is issued. At worst, you keep thrashing your cache loading data you're not going to read, delaying fetchin…

For everything? Obviously no.

But for all the crazy optimizations modern compiler do, I don't see how marking pointers for more then couple of them in a raw is that crazy

Re: Fast linked lists

#74

Post by hayley-patton »

stonemetal12 wrote: post #64
screcth wrote: post #25

Earlier quoted context omitted.

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

That implies you took the time to sort them, so your O(1) insertion time just became O(N log N). Sure, that cost is spread over how ever many inserts you did between GCs but it isn't O(1) anymore.

SBCL cheats and copies starting from the first cons cell that is referenced from outside the list; this tends to be the start of the list, and so traversing just works. The contiguous copying also ends when a cons cell which was already copied is found, so there can't be more discontinuities than there are cons cells referenced from outside the list, regardless of which order we discover the references.

Re: Fast linked lists

#75

Post by kolbe »

Xeamek wrote: post #72
kolbe wrote: post #39

Earlier quoted context omitted.

Given how much of today's computer needs are dependent on a database query, this is no surprise. Who cares about the micros you gain with added efficiency while there's a 100ms db query return in the path?

Apparently Apple and Intel do, since they introduced those changes into their silicon

Not every pipeline involves a db query.

Re: Fast linked lists

#76

Post by TheCondor »

torusle wrote: post #37

> Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects. I beg to disagree. In kernels, drivers, and embedded systems they are very common.

There are plenty of good uses for linked list and their variants. Like LRU lists come to mind; I couldn't bet that it's the most efficient way to implement them but they're pretty darn good. Then obviously things like breadth first search need a type of queue data structure. It often can come down to memory pressure, if you've got Gigs to spare, then allocating a contiguous block of memory for a list of something isn't a big deal, if memory is tight and maybe fragmented, linked lists can and will get it done. They have their places.

I did start to encounter some fresh grads with degrees that said "computer science" on them that couldn't answer some basic linked list questions. I was beginning to think it was a bad set of questions until I hit those kids. If you claim to know "computer science" and don't know what a linked list is, especially beyond some text books stuff, I'm probably not interested.

Re: Fast linked lists

#77

Post by vineyardlabs »

_xnmw wrote: post #51
torusle wrote: post #37

> Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects. I beg to disagree. In kernels, drivers, and embedded systems they are very common.

Why? Why would someone reach for a linked list in a kernel, driver, or embedded system?

Any time you have a computer interacting with the outside world in an asynchronous fashion you basically have to have some form of buffering which takes the form of a queue/fifo. A linked list is the most performant/natural way of modeling a queue in our ubiquitous computing infrastructure.

I/e in a DMA-based ethernet driver, the ethernet MAC receives packets asynchronously from the processor, perhaps faster than the processor can ingest them. So the mac interrupts the processor to give it new packets, and the processor can't sit processing the packets in the interrupt context, so it needs to put them into some ordered list for processing later when it has downtime. In a true embedded system, the memory for this list is going to be fixed or statically allocated, but you still don't really want to have an array-style list with fixed indexing, as you'll have to manage what happens when the index wraps around back to 0 etc, so instead you just construct a linked list in that pre-allocated memory.

I wouldn't say linked lists aren't really used in high-level applications, as I said they're used all over the place whenever you have external asynchronous communication, it's just that modern high-level frameworks/libs totally abstract this away from most people writing high level code.

Re: Fast linked lists

#78

Post by cabronerp »

aabhay wrote: post #26
EGreg wrote: post #24

Earlier quoted context omitted.

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?

This repo has a nice pub/sub implementation based on capnp: https://github.com/commaai/cereal/blob/master/log.capnp

Re: Fast linked lists

#79

Post by sfink »

ziddoap wrote: post #46
torusle wrote: post #37

> Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects. I beg to disagree. In kernels, drivers, and embedded systems they are very common.

> In kernels, drivers, and embedded systems they are very common. Out of all the programmers in the world, what percentage of them do you think work in the kernel/driver/embedded spaces?

First, my only guess is that everyone's guesses are going to be wildly wrong. People who work in such spaces will greatly overestimate. People who don't will greatly underestimate. (This is mostly due to how many comments I've read on HN that implicitly assume that most people's problems and perspectives are the same as the commenter's.)

Second, linked lists are useful in a lot more places than that. Probably a better proxy would be low-level coders. You almost always want a linked list somewhere when you're dealing with memory addresses and pointers. Maybe not for the primary collections, but there are always secondary ones that need to maintain a collection with a different membership or ordering, and vectors of pointers don't have many clear advantages over intrusive linked lists for those secondary collections.

Re: Fast linked lists

#80

Post by sfink »

SJC_Hacker wrote: post #62
dmitry_dygalo wrote: post #53

Earlier quoted context omitted.

Easier to avoid allocation errors, e.g. in the Linux kernel. I think Alice Ryhl mentioned it here - https://www.youtube.com/watch?v=CEznkXjYFb4

How do linked list prevent allocation errors? If anything it would seem to make them worse. My experience in embedded, everything is hardcoded as a compile time constant, including fixed size arrays (or vectors of a fixed capacity)

Intrusive linked lists eliminate the allocation entirely. With a vector, you have the Obj allocation and then potential vector-related reallocations. With an intrusive linked list, you only have the Obj allocation. So your code that adds/removes list entries does no additional allocation at all, it reuses a pointer or two that was allocated as part of the original Obj allocation. Often the list manipulation happens at a time when allocation failures are inconvenient or impossible to handle.
Post reply on HN