Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re^3: [OT:] Is this Curriculum right?

by eyepopslikeamosquito (Archbishop)
on Nov 24, 2021 at 22:46 UTC ( [id://11139087]=note: print w/replies, xml ) Need Help??


in reply to Re^2: [OT:] Is this Curriculum right?
in thread [OT:] Is this Curriculum right?

> And I’m aware of how important they are

Actually, linked lists have recently become completely unimportant! :) ... due to the mind-bogglingly high cost of cache misses on modern memory architectures. Linked lists tend to maximize cache misses, at least compared to the much more compact vectors.

This is analysed in more detail in The 10**21 Problem (Part 3) where Stroustrup noted that on modern memory architectures, C++ linked lists are typically 50 to 100 times slower than vectors.

Update: Much later I remembered Re: Data structures in Perl. A C programmer's perspective. (vector vs linked list performance).

Replies are listed 'Best First'.
Re^4: [OT:] Is this Curriculum right?
by LanX (Saint) on Nov 26, 2021 at 21:36 UTC
    > Actually, linked lists have recently become completely unimportant!

    For how long?

    Things which were relevant in the 90s became unimportant because of hardware a dozen years later to reappear as relevant after the same time span again.

    Example:

    • Multiplication on the Motorola 68000 was so slow (~74 cycles IIRC) that Mandelbrot sets were best implemented by precalculating a big lookup table in RAM (~8 cycles)
    • Later using lookup tables became obsolete by the speed difference between CPU calculations compared to RAM access.
    • Later caches became so big that big tables could fit again easily

    Lessons:

    • Efficiency of algorithms are effected by hardware
    • You can't always predict how hardware evolves.

    All this doesn't justify not to study linked lists:

    • they can be used in many contexts
    • with many advantages
    • are easily implemented (see LISP)
    • and performance is not always an issue.
    Now what exactly do you mean with a vector?

    If you mean something with equidistant entries, how would you implement an array of strings of varying length without links? And how are these string-links less likely to cause cache misses?

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery

      Sorry LanX, I confess I was indulging in the traditional Aussie pastime of stirring when I claimed that linked lists have become completely unimportant. :) You've made some excellent valid points in defence of linked lists. To answer your last question more seriously:

      How would you implement an array of strings of varying length without links? And how are these string-links less likely to cause cache misses?

      I'd try using the standard library: std::vector<std::string> ... hoping/trusting/assuming that this common case has already been optimized ... and googling indicates that most implementations of the C++ standard library do in fact use some form of Short/Small String Optimization (SSO) so that smallish strings are not stored on the heap, vastly improving locality of reference:

      A std::string typically stores the string as a pointer to the free store ("the heap"), which gives similar performance characteristics as if you were to call new char [size]. This prevents a stack overflow for very large strings, but it can be slower, especially with copy operations. As an optimization, many implementations of std::string create a small automatic array, something like char [20]. If you have a string that is 20 characters or smaller (given this example, the actual size varies), it stores it directly in that array. This avoids the need to call new at all, which speeds things up a bit...

      If I get time later, I may try to do some sort of benchmark of your interesting use case in both Perl and C++.

      I guess the point is what they think a vector is. I guess they think it like this (in R):

      v<-c(1:3) typeof(v) length(v) min(v) max(v) median(v) mean(v) append(v, 4) # shuffle(v) # sort (v)

      This yields in an interactive R session:

      [1] "integer" [1] 3 [1] 1 [1] 3 [1] 2 [1] 2 [1] 1 2 3 4

      Now the kids are forced to write down such stuff in German Pseudocode - with Umlauts. As we are in Germany. No kidding. Plus some UML diagrams. Just to come back to the roots. Or the original question. Now you can guess the next step? Best regards, Karl.

      Regards, Karl

      «The Crux of the Biscuit is the Apostrophe»

        > Now you can guess the next step?

        Rewrite the commands to püthon?

        map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
        > Now the kids are forced to write down such stuff in German Pseudocode - with Umlauts.

        That's the classical way to check examinations and written homework, it's not practical to have a whole class sitting in front of hardware.

        Pseudocode is good to demonstrate the algorithmic understanding while not worrying about syntax errors.

        The other extreme is googled "homework" code.

        This might be passing passing the syntax check and is somehow producing the required result because of a lot of try and error.

        But will often not demonstrate any understanding.

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery

        No. «Fünf hinein!» as my old teacher said.

        It should be:

        mische(victor) sortiere(victor)

        Now describe what a Übersetzer and a Bindelader is. In German as we are in Germany. You got one minute as we are in a hurry 🤪 Then write a class StandardChorobaBibliotkekDoppeltVerketteteListe. Don‘t google. Don’t read any man page. As real programmers never make it so. You got 5 minutes. Else you are durchgefallen.

        «The Crux of the Biscuit is the Apostrophe»

Re^4: [OT:] Is this Curriculum right?
by Marshall (Canon) on Nov 25, 2021 at 04:38 UTC
    I think that Stroustrup's concept as referenced, is completely out of context. Searching a "short" array or traversing a "short" linked list sequentially will always be relevant! A vector to a short linked list (like a hash table) is very efficient.

      Sorry, I don't understand the point you are trying to make. Are you suggesting that C++ vector is faster than linked list only for "small" containers? Note that Stroustrup measured up to half a million nodes, as confirmed in this talk by Herb Sutter (two years later). Herb likewise exhorts C++ programmers to prefer vector to linked list. Update: see also.

      As a journeyman C++ programmer, I greatly admire both Bjarne Stroustrup and Herb Sutter for their many contributions to C++ over so many years, especially their work on language standardisation. When they both exhort you to use std::vector (and std::map) as your default containers, I pay attention. ... which BTW has a nice synergy with Perl. At least, I've always enjoyed using Perl's analogous default containers (built-in arrays and hashes) ... and never felt the urge to write my own linked list class in Perl. :)

        I guess that I don't really understand what is meant by a C++ vector. A Perl hash table calculates a "vector" to a short linked list. Perl has an algorithm such that, in general, when these "short linked lists" become too long, Perl doubles the hash size and creates more "vectors". The lists associated with one vector, will become distributed amongst other vectors as more vectors become available. As long as each "vector" just points to a short linked list, this is just fine. You don't need one to one vector to object. You need vector to a few objects.

        BTW, if you are writing in Perl, just use the Perl array and use splice to insert or delete if you need to. I personally cannot remember writing Perl code that does that explicitly does that in the past decade. Mileage varies. There is no need for a specific linked list implementation in Perl.

        «…never felt the urge to write my own linked list class…»

        I talked about this issue with the boy’s teacher and it was like talking to a horse as we say in German. Best regards, Karl

        «The Crux of the Biscuit is the Apostrophe»

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11139087]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (6)
As of 2024-03-28 13:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found