4 ms·

When I moved from C/C++ to Java on the 90s, I was amazed how casually things like hash tables would be used. A single function might create a couple hash tables

When I moved from C/C++ to Java on the 90s, I was amazed how casually things like hash tables would be used. A single function might create a couple hash tables, do some data juggling and sorting, and solve a problem in like 20 lines of readable, performant code. In my experience, C coders almost invariably employ less performant algorithms and data structures due to the incidental complexity involved in memory allocation, pointer indirection, etc.

dehrmann 6y ago
This is where I always hope a JVM will learn that, use escape analysis to keep things off the heap (they can do this), swap out data structures for more efficient ones for small amounts of data, or tune data structure initialization params (they can't do this).
trhway 6y ago
absolutely. Few years ago i got back deep into C++ after 18 years of mostly Java, and i'm amazed, it is like travel back in time - we (a large C++ platform) are looping over vectors instead of using hashtables/maps, copying strings all the time (we have 4 major types of strings plus some minor ones), and don't get me started on multithreading and locking/synchronization - such an easy and natural thing in Java - even these days the people in C++ world is still seem to be hesitant to use locking and as result of that hesitance push themselves into a myriad of multithreading issues when they risk and/or are forced to use threads. It a sight to behold when a customer waits for that one core/thread to finish the operation on a 400 core 16TB RAM machine - if it were Java all the 400 cores would be burning, the performance would still feel kind of so-so, and the customer would be building up the nerve to upgrade to 800 core 32 TB :) >pointer indirection 30+ years ago, a student at University, i loved how pointers allowed to code algorithms efficiently and expressively compare to the non-pointer languages of the time. In the industry today the situation is completely opposite as correctly noted by the parent.
- bluGill 6y ago
  In many cases n is small enough that looping over a vector is faster than a hash lookup. The vector loop is very ry cache friendly, while the hash lookup typically involves a cache miss or two.
  - trhway 6y ago
    it would be for a vector where values are stored in the vector entries. Instead it is usually pointers to strings or objects. So you pull from memory by pointer (i.e. cache unfriendly) every string, compare, etc... And small n is usually small until customer actually generates couple orders of magnitude more of those objects than it was in test/dev :)
dan-robertson 6y ago
I feel like often the opposite can be true as well. Obviously hashtables are better for large collections but often collections are very small (sizes typically follow a power law; most strings will be smaller than the pointer to their first character; most collections will only have a few elements) and arrays can win here due to less indirection and better locality. Compare this to many functional languages (or lisps) where the most convenient data structure to hand is the singly linked list. It was already bad for performance when those languages were invented but in modern times they are relatively much worse than before. Sometimes I think that the performance of C programs come more from the fact that it such a massive pain to do anything in C that you can usually only do the simplest thing and this tends to be fast and reliable. The problem is that if you can’t do a simple thing it will either take a lot of refactoring or you’ll do a complicated thing and your program will randomly segfault. This is also my theory as to why languages like C have better libraries than lisp: it is such a monumental pain to do anything in C that people go to the small extra effort to package up their achievement into a library either for others or in case they need to solve the trivial problem again themselves. Improvements can them come later as needed but get shared. Compare this to, for example, lisp where the attitude is usually that libraries aren’t flexible enough and generally not that hard to implement yourself (so long as you aren’t so worried about data structures), and I think this is the reason there don’t tend to be so many libraries, especially for trivial things.
- mypalmike 6y ago
  Yeah I agree with this (apart from the lisp commentary, which I have no insight into).

dehrmann 6y ago

This is where I always hope a JVM will learn that, use escape analysis to keep things off the heap (they can do this), swap out data structures for more efficient ones for small amounts of data, or tune data structure initialization params (they can't do this).

trhway 6y ago

absolutely. Few years ago i got back deep into C++ after 18 years of mostly Java, and i'm amazed, it is like travel back in time - we (a large C++ platform) are looping over vectors instead of using hashtables/maps, copying strings all the time (we have 4 major types of strings plus some minor ones), and don't get me started on multithreading and locking/synchronization - such an easy and natural thing in Java - even these days the people in C++ world is still seem to be hesitant to use locking and as result of that hesitance push themselves into a myriad of multithreading issues when they risk and/or are forced to use threads. It a sight to behold when a customer waits for that one core/thread to finish the operation on a 400 core 16TB RAM machine - if it were Java all the 400 cores would be burning, the performance would still feel kind of so-so, and the customer would be building up the nerve to upgrade to 800 core 32 TB :) >pointer indirection 30+ years ago, a student at University, i loved how pointers allowed to code algorithms efficiently and expressively compare to the non-pointer languages of the time. In the industry today the situation is completely opposite as correctly noted by the parent.

bluGill 6y ago
In many cases n is small enough that looping over a vector is faster than a hash lookup. The vector loop is very ry cache friendly, while the hash lookup typically involves a cache miss or two.
- trhway 6y ago
  it would be for a vector where values are stored in the vector entries. Instead it is usually pointers to strings or objects. So you pull from memory by pointer (i.e. cache unfriendly) every string, compare, etc... And small n is usually small until customer actually generates couple orders of magnitude more of those objects than it was in test/dev :)

dan-robertson 6y ago

I feel like often the opposite can be true as well. Obviously hashtables are better for large collections but often collections are very small (sizes typically follow a power law; most strings will be smaller than the pointer to their first character; most collections will only have a few elements) and arrays can win here due to less indirection and better locality. Compare this to many functional languages (or lisps) where the most convenient data structure to hand is the singly linked list. It was already bad for performance when those languages were invented but in modern times they are relatively much worse than before. Sometimes I think that the performance of C programs come more from the fact that it such a massive pain to do anything in C that you can usually only do the simplest thing and this tends to be fast and reliable. The problem is that if you can’t do a simple thing it will either take a lot of refactoring or you’ll do a complicated thing and your program will randomly segfault. This is also my theory as to why languages like C have better libraries than lisp: it is such a monumental pain to do anything in C that people go to the small extra effort to package up their achievement into a library either for others or in case they need to solve the trivial problem again themselves. Improvements can them come later as needed but get shared. Compare this to, for example, lisp where the attitude is usually that libraries aren’t flexible enough and generally not that hard to implement yourself (so long as you aren’t so worried about data structures), and I think this is the reason there don’t tend to be so many libraries, especially for trivial things.

mypalmike 6y ago
Yeah I agree with this (apart from the lisp commentary, which I have no insight into).