Hacker News Reader

Comment by School-Cotton | Hacker News Reader

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).

View on HN

I can't read the link, because twitter links never work on my phone... always 'something went wrong' and saying I am rate limited.

Same thing happens to me frequently. Try reloading? That usually works for me.

I 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

This happens to me every time but if I request desktop mode it always works 100%. Might be worth a try.

As 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.

Thanks for the hint. That could be the reason I get this on nightly since .. about four weeks (or six weeks? something like that). Seems to concede with the time the new privacy protections went on by default.

It's not recent - I've had this for years.

I've only just noticed it, but mostly because I've forced myself not to install the Twitter app nor login to my account on the particular device I've been experiencing all these "Something Went Wrong" errors. I assumed it was a "feature" to encourage people to login to the app caused from a bug somewhere in the ad stack, and this seems to corroborate that hunch.

No, it's not exclusive to Safari. It happens all the time for me in Chrome on Android.

Based on referrer I think. Links from big sites like reddit or hn are often rate limited. Reloading the page wipes referrer and fixes it.

This is exactly why I stopped using twitter (that and no matter how many thousands of people I have in my blocklist there is a Trump tweet/comment/quote in their all the time. You can’t ever escape it).

I wonder what kind of product decisions have led to “we rather piss off and lose thousands of customers than fixing our problems”

I 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.

On 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.

Very 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.

>...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?

How does the debugger know that?

Short-answer: The debugger (in Windows) sits between the first and second and chances, if I recall correctly, to "help" the user by displaying a dialogue notifying them that 'x' is unhandled. Anything in second chance has reached the kernel for handling and is no longer in the user space.

You'll often see this (second chance) as exception entries in the Windows Event Log for things like kernelbase.dll, which points to the offending instruction set. The handler in this space typically invokes Watson to generate Watson reports because it was unhandled elsewhere.

The debugger prevents all of that.

Of course, in JIT, you have things like read-ahead for first-chance exceptions...

A good book, in the Windows space, that cannot recommend enough, is Windows Internals[0]. They include how the managed and user spaces interact and coincide with the native and kernel spaces and how all of that transpires, such as how an exception in user mode transitions to kernel before Watson report is created.

There's other in-depth resources[1], as well, if books aren't your thing.

[0] - https://docs.microsoft.com/en-us/sysinternals/learn/windows-...

[1] - https://doar-e.github.io/blog/2013/10/12/having-a-look-at-th...

Cache is also an extremely limited resource and the more you waste the less other programs have to work with, slowing them down too, some of what your program pushes out of the cache could be slowing down disk and network processing. There's a tragedy of the commons effect happening in our CPU's.

That doesn't mean it's always worth otimising for, but it's worth remembering yours isn't the only process running.

The 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.

Sure they are widely used, but are they the main data structure in any CPU-bound hot loops? I'd be surprised.

More 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.

Arrays get you spatial locality :)

So long as they dont span across a page boundary.

Huh? Spatial locality knows no bounds. The hardware might not automatically prefetch across page boundaries but the application can initiate the fetches itself.

And, 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)

Indeed, 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.

I 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.

That 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.

That’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?

> 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".

True. Managing the nervousness of awkward engineers during interviews is a whole topic in itself.

In 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.

I would have hated this problem. There are so many things unclearly specified. What allocator is used to allocate this linked list? Did you use a small-object pooled allocator that essentially places the nodes of a linked list sequentially in memory? Did you permute the order of the nodes afterwards? Is each node even located in separate pages, using up the TLB as you dereference? Could there be page faults when you deref the next field? Without knowing how the nodes are laid out in memory, it is impossible to answer.

Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming.

> Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming.

Didn't OP already imply that the point of the question was not as much to get a specific answer, but to probe whether or not the interviewee knows about all the factors that need to be considered?

So why not ask exactly that? "What are some of the factors and tradeoffs to consider when implementing X / deciding between X and Y, etc.?"

You would have done great with this question :)

Asking "Do you know the magic answer I happen to know?" questions is the great sin of technical interviews. Instead the goal is to keep the candidate comfortable and semi-confident while digging out their mindset about relevant technical issues.

The steps to iterate the array should impose no overhead on a superscalar processor. It’s a different situation on a simple embedded processor, but the range of possible answers for memory:ALU ratios, cache line size, cache latency, allocation patterns, MMU behavior and some other factors make this an ill-posed question.

Pedantic nitpick: that is not the simplest LL algorithm. It is more complex than empty().

The question is intentionally ill-posed. The goal is to find out how you model the problem, not that you guess some magic number.

Asking broken questions seems like a strange way to find out what somebody knows.

Personally, I tend to get the impression I might not actually enjoy the work at a company that concentrates on low-level questions like that.

I happen to like JS and node a lot, for very pragmatic reasons. I've also dabbled in Go and Rust for equally pragmatic reasons. It does help to understand some of the things under the covers when you need them. That said, for a LOT of jobs, code that works and is business rule correct is more important than if it takes a blink of an eye or three.

I tend to prefer a first pass in node/js, and then break things off or optimize as needed in practice. Scale !== raw performance and is often more important.

The candidates were applying for positions in game development at a company that made high-end 3D mobile games. Raw performance translated directly to retention and therefore revenue there.

Working 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.

It 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.

I have never done detailed CPU performance work.

I am however not Spartacus!

Aren't linked lists still in hashtables? Or have hashtable implementations changed?

Reply on news.ycombinator.com