Also I wouldn't say that the same algorithm would be faster in C, there is no reason why C++ can't be as fast as C, even idiomatic modern C++.
The biggest reason to write in C over C++ is simplicity and higher level of control over algorithms and data structures. Portability is another reason though.
For simple functions, templates are usually always a pure win. For example, C qsort is horrible. Function pointer to a otherwise so inlinable small sort function is always going to get beaten by C++ template based sort.
But if each iteration of loop needs to fetch 10 kB of instructions because of specialized separately compiled templated forms, suddenly pointers win again. It can also invalidate TLB, branch predictor, etc. caches.
But most cases templates are a win. Just remember microbenchmarking can really mislead here, if the program as whole has an icache bottleneck as a consequence.
I'm not suggesting like, never used linked lists or anything. I just think that most computer science is predicated on an abstract machine with predictable memory latency, and naturally people tend to design things with that in mind, while in reality, unless you're processing data sets so large that memory latency is insignificant, an O(1) operation might be way slower than an O(N) operation.
struct City {
char *name;
int popstrat[5];
float bounds[2];
};
I certainly agree with you on the weight given to O notation though.
There is no way a linked list will be the fastest way to do this on modern hardware. A big part of the reason it is so fast I think is because intel cpus are so good at prefetching, caching, and instruction reordering.
If you are talking about kd-trees specifically you might want to ask questions if you have any. I've done 4 full implementations, each one with more refinement.
I see more what you are saying below but I can't reply to it. First, you could have that a vector of that struct and memmove the elements on swap, which wouldn't be too bad performance-wise. In a struct of arrays set up it wouldn't perform as well since the swaps would be multiple cache-incoherent reads and writes (sort of as you said).
Sorting an array of ints will be very fast and likely the fastest way to do it. Then you can structure your data however you want and re-write it once you've sorted it.
Introsort and quicksort can be done in place using an array, but constant spatial complexity isn't always priority one. Some of the more recent algorithms aren't constant (timsort, spreadsort).
Linked lists (doubly linked lists) still have valid uses, but it's generally better to use an array (or vector) until you can justify otherwise.
I can promise you that if there is a linked list in a performance crucial place that it could be sped up a non trivial amount.
Linked lists can be convenient and they can be consistent, but they aren't fast. The pointer chasing hurts performance. The extra heap allocations may or may not be able to be avoided. The alternative is something like a vector of pointers (although I would in practicality not being using a raw pointer, it would be some sort of larger data structure). That will be faster with the exception of resizes, which should be fast in general, since what they hold should be small, but they won't be consistent.
Beyond that there is the idea that concurrency could mean that needing to lock a data structure makes a linked list less of an outlier because the time that it would need to remain locked would be smaller. In that case I think a vector would likely still be much better in general, since you could keep the current index to write to in an atomic, which wouldn't require a lock.
Most lower-level memory allocators e.g. tend to use linked-lists afaik because you end up removing and inserting slabs a lot, the Linux kernel also makes wide use of linked lists as well. If there were substantial performance gains to be made without other large tradeoffs it would have been done.
EDIT: Some additional info: http://www.jikos.cz/jikos/Kmalloc_Internals.html
Vectors/Arrays are great when you don't care as much about the total memory consumption, but you want to reduce the amount of heap fragmentation.
A downside to using arrays like this, and likely a leading reason you don't see them used that much in the linux kernel is that every once and a while an insert is going to force a realloc which takes a relatively long time. std::vector and the like mitigate this by reserving more space than they'll need and so they minimize the # of reallocs required.
There is also performance implications to doing std::vector<myStruct> vs std::vector<myStruct*>. The later can very easily mimic the same cache coherence issues that happen with a linked list of myStructs.
So when we are talking about speed in terms of millions of items in some data crunching program, vector is almost always going to win out. But if we are talking about minimal memory footprint where we want consistent timings , linked lists are a contender.
If it weren't for pointer overhead I'd just throw everything into a graph, but 64-bit addressing makes that expensive.
Even then, that might be a good strategy if inserting into a vector type data structure required a realloc everytime. However, most implementations use an exponential strategy, so for a million item vector grown one at a time, you'd see only 10-20 reallocs. Which is to say, the realloc problem is only a problem in memory constrained -- think embedded or kernel -- systems where a memory overhead of 1.5-2x isn't viable.
You can do the same thing -- and some linked list implementations do -- with linked lists, where you grab a block of nodes at a time. If you don't though, just in inserts, the vector will be faster. Mallocs are non-trivial in most applications and can easily become the bottleneck.
I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list, nevermind random access. Cache issues really, really do matter. If you want to see this in action and happen to have a SoC dev board around, disable the data cache and run some benchmarks with vectors. If you re-enable it, you will easily see a 10x-20x improvement.
If you watch https://www.youtube.com/watch?v=YQs6IC-vgmo, he goes into some of the use cases and some benchmarks that might be compelling to you.
Or userland, when your software is processing hundreds of millions of datapoints - each with several additional independent properties.
> I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list...
No, I'm well aware of the effects of locality - the linked list of arrays is an easily tuned compromise between speed and memory consumption (leaning much more towards memory considerations).
I don't get the point about additional independent properties. Size of the struct changes the memory you need to grab, but not the number of reallocs you have to do.
See: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector... for actual benchmarks on this. If you disagree with these benchmarks, and find your own results to be different, I'd love to see the write up on that, and I'm sure I'm not the only one.
You've got hundreds of millions of data points to slurp into ram, each data point may have additional properties from a fixed set, data points are independent of one another - so not a good fit for a graph, adjacency matrix, etc. Disk access outside of the initial slurp is a no go, so we have to make this fit in ram.
Throwing the data point into a struct is nice and easy, plus it eases the system call overhead for m/re/callocs. But you've got a bunch of wasted space in padding, locality is gone, compressibility is much more limited.
Throwing the data into a bunch of parallel arrays is about the most memory efficient way of doing it, especially considering the ease with which you can use delta encoding and bin packing. But now every memory/sort operation is magnified by the number of arrays you've got.
As far as a writeup, I'm working on a succinct atomic map for strings - I look forward to releasing the code once I finish... and rewrite it in such a way that my employer doesn't sue me (it isn't organic to the business, but better safe than sorry).
Not entirely clear on how the indexing would work to your benefit with parallel arrays. If there is a 1 to 1 mapping between datapoints to items in each || array, the memory consumption is the same as a struct, so I assume thats not it.
It almost sounds like you are describing a (possibly non-numeric? non-homogenous?) sparse matrix, which are usually worked with in vastly different formats for construction vs manipulation vs iterating over.
Not that I know of, sorry.
> Not entirely clear on how the indexing would work to your benefit with parallel arrays.
Lets say that we have data that would be represented in an array of structs like so:
typedef struct
{
char* name;
int age;
} prsnT1;
prsnT1* peopleAOS = calloc(100, sizeof(*peopleAOS));
typedef struct
{
char** name;
int* age;
} prsnT2;
prsnT2* peopleSOA = malloc(sizeof(*peopleSOA));
peopleSOA->name = calloc(100, sizeof(*peopleSOA->name));
peopleSOA->age = calloc(100, sizeof(*peopleSOA->age));
> ... which are usually worked with in vastly different formats for construction vs manipulation vs iterating over.
Yup, classic abstract data type - doing OO in C the hard way :)
Functional programming is much more popular in academic circles than in industry. I think academics tend to hand wave away practical concerns like cache coherency as "an implementation detail" or as an "exercise for the reader." Big O times are often considered, but rarely do researchers make a career off of "how well does this fit into an X86 L3 cache"
So yes, functional programming tends to depend on linked lists, and that's probably why you don't see it in things like the game industry. This might change in the future, for instance, I could see it being the case where having provably immutable memory could allow processors to manage more memory efficiently, but I don't think you can have a fast language that considers the CPU as an abstract entity; you have to design these things in.