7 ms·
Very interesting thread -- if you're the type of person who comes to the comments before deciding whether to read, I recommend it. I'd also like to point out t
by umanwizard 7y ago
Very interesting thread -- if you're the type of person who comes to the comments before deciding whether to read, I recommend it.
I'd also like to point out that today in 2019, linked lists perform like absolute dog shit in many real-world contexts even where they have the best big-O notation.
Somebody jumping straight to a solution based on linked lists without at least mentioning memory latency is a sure-fire sign that they have never done detailed CPU performance work. (Which is not necessarily a requirement for most programmers, but it's one piece of signal among others).
- mav3rick 7y agoArrays get you spatial locality :)
- qtplatypus 7y agoSo long as they dont span across a page boundary.
- shereadsthenews 7y agoHuh? Spatial locality knows no bounds. The hardware might not automatically prefetch across page boundaries but the application can initiate the fetches itself.
- XMPPwocky 7y agoAnd, regardless, speculative execution will happily figure out that, hey, the next loop iteration starts with > add rsi, 4; mov rbx, [rsi].d and rsi is 0xDEADBFFC, so rsi+4 is 0xDEADC000, so let's speculatively load that address.... Extra bonus - the compiler may be able to auto-vectorize that. A linked list, on the other hand... hardware can't tell what to prefetch in > mov rsi, [rsi].q; mov rax, [rsi+8].d because it has no idea what rsi is going to be after the first instruction. So it's not just cache locality (which is huge!), it's also the ability of the CPU to actually run things in parallel, instead of serializing everything (and, again, if you're really lucky, the compiler will auto-vectorize the array code)
- shereadsthenews 7y agoIndeed, speculative loads from pages that you don't even own has been a big big topic on this site for over a year. There's no respect for page boundaries in the hardware.
- sitkack 7y agoI think Sandybridge or Skylake, made this exact optimization that in turn speeds up execution of vtables and interpreters by reading through a pointer so it might indeed be faster on some architectures. Your point stands though, that linear array access will have similar performance everywhere. Where as LL will have a wider envelope due to speculative loads.
- XMPPwocky 7y agoThat works for vtables and interpreters because the vtable/interpreter jump table will be hot and in cache. It doesn't help for linked list iteration unless the next element in the list is in L1 cache.
- qtplatypus 7y agoOn the otherhand for many applications memory latency isnt an issue. If network and disk io is your bottelneck investing time in optimising that part of the code.
- umanwizard 7y agoVery true, which is why I said "many real-world contexts" and not "always", and "CPU performance" and not "network-bound performance". Anyway, a candidate who mentioned all (or even some) of this to me and then went on to write a linked-list solution after explaining the tradeoffs would be well ahead of the curve, for me, relative to someone who has just grinded Leetcode and not thought much about what is going on under the hood.
- maxheadroom 7y ago>...and not thought much about what is going on under the hood. This doesn't make sense to me, the way you've worded this. A person needn't have ever been exposed to linked lists to understand "what's going on under the hood" - which is a far bigger picture than you're trying to get something as confined as linked lists to fill. You're seemingly saying, "You don't know fruit because you know fuck-all about dragonfruit," and that - to me - is a pretty myopic take on things; especially, in a growing cloud-centric world. For example, I would expect that someone who could tell me how the debugger knows where their exception handler is (to be able to handle their exception) would be a better caliber for determining whether they've "thought much about what is going on under the hood" than someone who could just tell me how performant a linked list is, yeah? In the former, it's actually having had to understand what it's doing. In the latter, it's just 'x' type that - maybe - you get exposure to because of uni settings. ...but, to give credit, maybe I'm misunderstanding your intentions, as you've worded them?
- oblio 7y agoHow does the debugger know that?
- 7y ago
- BurningFrog 7y agoI have never done detailed CPU performance work. I am however not Spartacus!
- cortesoft 7y agoI can't read the link, because twitter links never work on my phone... always 'something went wrong' and saying I am rate limited.
- umanwizard 7y agoSame thing happens to me frequently. Try reloading? That usually works for me.
- ignoramous 7y agoI block 3p JavaScript and I never seem to be able to use Twitter without multiple re-loads. So, I usually unroll threads via threadreader. Here's the current one: https://threadreaderapp.com/thread/962424365819277312.html https://threadreaderapp.com/thread/962424365819277312.html
- gmjosack 7y agoThis happens to me every time but if I request desktop mode it always works 100%. Might be worth a try.
- saagarjha 7y agoAs far as I can tell, this is some sort of thing that Twitter does to Safari users because it can't fingerprint them well and thinks it might be abuse.
- anbop 7y agoAren't linked lists still in hashtables? Or have hashtable implementations changed?
- rlp 7y agoSee linear probing hash tables, the items are stored directly in the main array with no linked lists.
- corysama 7y agoThat’s why I include a LL question in my code interviews. But, my question is about the simplest possible LL algo: Assume I have the simplest possible linked list of integers in basic C. Just struct Node { int data; Node *next; }; Assume I also have a plain old C array of ints. I can trivially iterate through both of these data structures and sum up the ints they contain. Either way it’s a linear, O(n) operation. However, everyone knows linked lists are slower than arrays. The question is: How much slower? The most common answer I get is “2x”. This is always after working carefully through the steps to iterate a list and ignoring steps to iterate an array. I like the question because it tests 2 things: 1) Are you aware of the existence of cache? Many people I’ve interviewed have only heard of it vaguely. 2) If you don’t know the answer, are you at least curious enough to ask what the answer is and have a conversation about it?
- skrebbel 7y ago> 2) If you don’t know the answer, are you at least curious enough to ask what the answer is and have a conversation about it? This is a bad test. People might be too nervous to ask, especially if they just feel like they've failed a test. You're testing for "is this person comfortable in an interview setting", not for "is this person curious enough".
- corysama 7y agoTrue. Managing the nervousness of awkward engineers during interviews is a whole topic in itself.
- skrebbel 7y agoIn fact, I'd wager that one of an interviewer's primary goals should to find a way to fully disregard someone's interviewing skill. Search hard for questions that a sweaty super-nervous introvert would be able to do just as well as a confident natural talker. Find wording that lets you give hints / explain the question better without the interviewee going "oh no, a hint, that means i failed this step!". I personally think this is very hard to get right, but it has to be a top prio. It's much harder (and much more valuable) than cooking up a sufficiently difficult whiteboard coding question.
- com2kid 7y agoWorking on embedded with 1 cycle sram and a cpu with minimal/no concept of pre-fetch has the advantage that linked lists become nearly as fast as arrays, just 2x slower! But outside of that use case, yeah, Linked Lists are generally bad.
- misterman0 7y agoIt seems more appropriate to say, Linked Lists are generally bad [when used as replacement for arrays]. LL aren't generally bad at doing what only linked lists can.
- monocasa 7y agoThe Linux kernel is almost entirely built off of linked lists. Are they the best fit for every siuation? No. Have the rumors of their demise been greatly overstated? Yes.
- umanwizard 7y agoSure they are widely used, but are they the main data structure in any CPU-bound hot loops? I'd be surprised.
- monocasa 7y agoMore often than you'd think. The simplification of memory management when you have intrusive linked lists is a huge win, both for perf and correctness.
- mrmuagi 7y agoI looked through the linux source net code and their usage is actually ubiquitous, but they are paired with hashes and trees. Storing your entire data in a linked list, I agree is horrible, but using linked lists within a hash bucket for keeping entries was acceptable, but because of collision attack causing DDOS susceptibilities, trees were preferred moving forward. When we talk about drivers, from my little exposure (mainly fixing kernel panics), DMA, and cyclical arrays for buffers, I don't recall seeing any linked lists in performant codepaths (it's common to use linked lists for an object pool, like descriptors, but these are O(1) because of tail operations (doubly linked)). But I did see descriptors being put onto cyclical buffers and deferenced, which is the same cost of a pointer deference in a linked list step traversal.