Hacker News Reader

Comment by BeetleB | Hacker News Reader

> Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one.

I think your parent's point is that if you're a C++ programmer, recognizing that vectors outperform other data structures for most use cases is what separates a good engineer from a great one. Often even for things that require lookup (i.e. vector outperforming a set).

During code reviews, a senior C++ programmer in my company (formerly sat in the C++ standards committee) would always demand benchmarks from the developer if they used anything else. In most cases, using representative real world data, they discovered that vectors outperformed even when the theoretical complexity of the other data structure was better.

A great engineer knows the limitation of theory.

Of course, my comment is only regarding C++. No guarantees that vectors are great in other languages.

View on HN

> Often even for things that require lookup (i.e. vector outperforming a set)

I am always uncomfortable using higher algorithmic complexity. Sure, for small data sets, the vector will outperform the set, but it may not stay small forever. I may waste a millisecond now, but at least, I won't waste an hour if the user decides to use 100x the amount of data I initially considered. And using much more data than expected is a very common thing. It is a robustness thing more than optimization.

If you want both, there are staged algorithms, a typical example is a sort algorithm that goes insertion -> quicksort -> mergesort. Insertion sort is O(N^2), but it is great for small arrays, quicksort is O(N log N) on average but may become O(N^2) in some cases, and mergesort is guaranteed O(N log N) and parallelizable, but it is also the slowest for small arrays. For lists, that would be a list of vectors.

I like the staging idea, but curiously I haven't seen any papers investigating this.

Obviously, there is an overhead cost of the staging itself, which hits the use case for small data, and there is the question "From what data size onwards to use what algorithm?".

For example, I just had a look at sort in Clang's STL implementation, which seems to set a boundary at N=1000. Since the number is a multiple of 10, it looks like it might be arbitrarily picked, in any case there is no paper references in the comments to back it up.

Are people aware of formal studies that explore whether it is worth the trouble to inspect data structure and then to dispatch to different algorithms based on the findings?

You're saying you think there's still optimization to be done re. the N=1000 constant?

Other than that, I'd suggest that big O complexity is already telling you that the inspection is worth it. Assuming inspection of an array is constant.

> Sure, for small data sets, the vector will outperform the set, but it may not stay small forever.

In over 90% of SW applications written in C++, there is little to no uncertainty on the size of the data set. Most applications are written for a very specific purpose, with fairly well known needs.

If my data set is size N, and I can benchmark and show the vector outperforms the theoretical option up to, say, 20N, it's a safe choice to go with vector. Doing these analyses is engineering.

In any case, it's almost trivial to swap out the vector with other options when needed, if you plan for it.

I hope that senior engineer is also the one person, who will refactor things, if ever there are more elements in any of those vectors, making linear search slower than an actual set or other data structure. Oh and of course that senior engineer will also hopefully be the one monitoring the lengths of all those vectors in production.

> vectors, making linear search slower

The standard library gives you plenty of tools to maintain and search in a sorted vector. Often enough still faster than maps.

> Oh and of course that senior engineer will also hopefully be the one monitoring the lengths of all those vectors in production.

Doesn't a std::map have more space overhead than a vector?

I believe he was referring to the number of elements in a vector, to know when to swap with a different data structure - not the size in bytes.

But to your point - I once needed to do a key/value lookup for a large data set, and so of course I used a map. Then I ran out of RAM (had 80GB of it too!). So I switched to a vector and pre-sorted it and used binary_search for lookups (data set was static - populate once and the rest of the codebase didn't modify it). And of course, the RAM consumption was less than half that of the map.

Just describe your sorted list as "a balanced binary tree with implicit child links" and then you get credit for being fast, space-efficient, and using fancy data structure.

> [V]ectors outperform other data structures ... even for things that require lookup (i.e. vector outperforming a set)

This is something I've heard before (not often benchmarked) and it makes intuitive sense, and sometimes I've also told it to myself in order to not feel bad for writing O(n) where n is always small.

But somehow, reading this snippet, I'm reminded that the vector does not maintain the semantic reminder that it's used in a key/value use case. So it has me thinking there should be a map/hashtable/dictionary interface that's really just a vector with linear lookup.

Then I think, hmm, maybe the standard containers should just do that. Maybe the authors of those should have some heuristic of "when to get fancy".

I think the cases where lookup is faster for a linearly scanned vector is where the hash computation overhead is greater than a linear scan. Assuming you have a good hash implementation, that should be true only for a small number of entries, where you need to determine "small" by measuring.

I think it's about locality and quickness of compare.

So if you have a small data structure and/or large cache, and the key is not complicated.

Even if the key is cheap, that it isn't in cache means that vector will be faster just because we avoid the cache miss of loading the value into memory.

Std::find_if works great if you want to treat a vector like a map. Plus you can have different keys if that is useful for your problem (look up employee by name, id, or address?)

These are flat_map, flat_set, flat_hash_map, etc ...

See: https://en.cppreference.com/w/cpp/header/flat_map

I believe that flat_map and flat_set at least are sorted, so that binary_search/lower_bound can be used for lookups.

Linear search generally does outperform for small collections though (it’s better for caches and the branch predictor).

C++23! The future is here.

Reply on news.ycombinator.com