C - Randomized order String

[Unimportant]

On 21.1.2017 at 5:49 PM, M.Yurizaki said:

With a linked list, once you use a word, you remove it from the list. That avoids the problem of checking if it's used or not because it simply doesn't exist anymore. Traversing becomes increasingly faster as you use more words. You cannot do that with an array with a mixture of valid pointers and NULLs because you still have to check if the entry is NULL or not.

If this were a serious project and OP wanted to expand on it, then using a static array has issues. Is it easier to code and read and such? Yes. Is it easier to maintain? Arguably not depending on the data size you're working with. Besides, once you have your linked list logic down, you never have to touch it again.

I've actually spent this sunday afternoon trying out both implementations. (with gcc 5.4.0 on ubuntu 64 bit, tested on both a Q6600 desktop and i3 laptop). Testing was done with a very long string so time differences have a chance to add up into something measurable.

 

Iterating trough the array searching for the n-th pointer while skipping NULL's is VASTLY faster then traversing a linked list looking for the n-th word. After profiling and some runs with cachegrind the reason is clear: Linearly traversing a array is one the most cache friendly things you can do, you're nicely running trough cache-lines and the speculative predictor can bring in the next cache-line in advance because it can easily understand the access pattern.

 

Traversing the linked list however is cache-miss upon cache-miss, there is no way for the speculative predictor to know what address the next node in the list will be at, as a result it will constantly need to bring in data from main memory which is a performance disaster.

 

EDIT: More testing shows that performance actually drops when the linked list shrinks. If you are lucky, most nodes of the list may be allocated in memory next to each other (but this is certainly not guaranteed), initially lowering the chance of cache misses and showing performance not much slower then the array solution. However, once you start removing random nodes from the list performance drops of a cliff as the list now becomes more and more fragmented in memory, making cache-misses ever more a certainty, right up until the point where the list becomes so small it starts negating the cache-misses effect.

 

I can't help but stress how problematic this becomes. The stall time a single cache miss takes on the linked list solution is enough to traverse the entire array multiple times for a 20 word sentence.

/EDIT

 

Additionally, operations on the array may also be vectorized (there seems to be a SIMD instruction to compare a range of array alements to a given value (NULL, for example) in one go), whereas operations on a linked list obviously cannot be.

 

I guess that after a while a fondness of linear memory accesses becomes second nature, and with good reason it seems.

 

All in all a nice lesson in how all these Big O time complexity calculations often fall apart in reality when your less complex algorithm breaks caching/pre-fetching.

 

(Second opinion: https://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/)