The second i saw the tov benchmarks i thought: no way these benchmarks are well done if thats the result, just a single look at the used datatypes in the benchmarks make this obvious. Nice to see someone actually took the time to put some numbers for the compare
I'm kind of confused about the dispatch benchmark. I took a look at the tov code and it seems to be testing dynamic dispatch. Changing the Rust code seems to be changing what the benchmark is actually measuring.
Obviously, "faster than rust" is hyperbole, you can basically always produce faster code in a lower level language for any given task, we've gone through this sort of thing a million times, but it is entirely possible that tov produces faster code for dynamic dispatch in this particular case
Tov's optimizer might be monomorphizing the dynamic dispatch into something that works the way the fast Rust version does. Which is a point in its favor, except that dynamic dispatch as in this example isn’t idiomatic Rust; most programmers would reach for enums as in the rewritten test.
It's also not always a clear-cut thing. The hand-optimised version is not semantically identical, because it's now supporting closed-world types whereas the original was open-world. This is fine if you're doing whole-program optimisation and not loading plugins. LLVM can do this for C++, so probably could do the same for Rust.
But the real win comes from that conversion: it's a closed world, which means the call site is statically provably polymorphic not megamorphic. And that composes with the fact that all of the implementations are 3-4 instructions, so inlining is a clear win. Especially once you realise that CSE will unify the rectangle and triangle implementations, so you actually end up with something like two branches in the final version, possibly even one branch and a conditional move. Something like (C-like pseudocode):
if (tag_is_circle)
{
result = PI * field0 * field0;
}
else
{
tmp = field0 * field1;
tmp1 = tmp * 0.5;
// Conditional move
result = tag_is_triangle ? tmp1 : tmp;
}
The initial check is a branch because most architectures don't have predicated loads (you could make this faster if you had a non-trapping load, otherwise the load of the second field may trap so has to be hidden behind a branch).
But the fact that this is slower for this specific example is misleading. It's not removing the dynamic dispatch at execution time that makes it fast, it's the subsequent optimisation. If you want to preserve the original semantics, then other implementations may be faster.
There is a good argument to be made that a source language can be faster if it doesn't mandate any of these implementation choices and, ideally, conveys enough information to allow the compiler to choose the right one. Implementations of Smalltalk-family languages typically do this via profiling, but that may not show up in such a small benchmark.
You can call me a bad amateur Rust programmer, but I didn't know about ahash because std::collections::HashMap has been fine for me since I started writing Rust.
That's kinda the only part where I am not fully on board with the assessment. Quoting from the docs "While its performance is very competitive for medium sized keys, other hashing algorithms will outperform it for small keys such as integers as well as large keys such as long strings, though those algorithms will typically not protect against attacks such as HashDoS" - this does not read "omg it's slow" to me. But looking at the benchmark, it still seems ok.
For most real-world use cases, the standard hashmap is plenty fast. But when your application is meaningfully bottlenecked by hashing, or when you have a benchmark solely testing map insertions, it quickly becomes a test of the hash algorithm, rather than the surrounding language. Though the authors here don’t mention what hashing algorithm tov/typescript uses and whether it is intended to be cryptographically secure, which I think would be worth mentioning for completeness.
Yeah exactly. It does different things but probably could have been chosen better or documented better. I'm a bit confused why a 2nd (fast) one would only be on crates, not in std, but I guess this being the default is ok.
The standard library authors generally try to keep it small and lean on the crate ecosystem for non-default options. In the case of hashes, they probably wanted to keep a single, cryptographically secure default option, and anyone who wants to opt into a less secure option does it explicitly and intentionally by going to the crates ecosystem or writing their own, rather than choosing a less secure option from std.
To be clear, it’s not HashMap that’s slow[ish], it’s the default hash function (SipHash). IIRC HashMap uses a state of the art hash table algorithm (is it SwissTable?)
I use HashSet<u64, rapidhash::RapidHasher> in a bunch of hot loops (eg. set of visited nodes in a Breadth-First Search). Even with the extra restriction to keys <= 50B it's really hard to beat with custom structures.
The best I came up, besides bit vectors, with is using Vec<HashSet<u32, rapidhash::RapidHasher>> by storing each value n as n % (1<< 21) in the (n >> 21)th bucket (I have no idea why 21 gives the best perf). it saves half the memory (because we only store a u32 per value) but performance-wise it's only 5% faster.
Right now, 30% of the runtime of a multi-day script is spent in contains() :(
You are right, I guess, but that's picking on a maybe vague phrase I used. If the user talks about "the HashMap (implementation)" then it would not work without a hash table algorithm, so I was talking about the whole thing. I had understood that, thanks for clarifying though.
Yes. People often misunderstand the goals of Rust/C/C++/etc: They give you as many tools as possible to achieve bare metal performance, available to be used whenever they are needed. All that extra stuff kinda piles up and makes people confused.
Languages like Tov just try to make common use cases as fast as possible, but as soon as you leave that space, you soon run out of official tools to optimise things with and you end up working against the language. NGL it's super fun optimising things in spite of the tooling, but just not at work.
xnacly | a day ago
The second i saw the tov benchmarks i thought: no way these benchmarks are well done if thats the result, just a single look at the used datatypes in the benchmarks make this obvious. Nice to see someone actually took the time to put some numbers for the compare
mplant | 18 hours ago
I'm kind of confused about the dispatch benchmark. I took a look at the tov code and it seems to be testing dynamic dispatch. Changing the Rust code seems to be changing what the benchmark is actually measuring.
Obviously, "faster than rust" is hyperbole, you can basically always produce faster code in a lower level language for any given task, we've gone through this sort of thing a million times, but it is entirely possible that tov produces faster code for dynamic dispatch in this particular case
snej | 17 hours ago
Tov's optimizer might be monomorphizing the dynamic dispatch into something that works the way the fast Rust version does. Which is a point in its favor, except that dynamic dispatch as in this example isn’t idiomatic Rust; most programmers would reach for enums as in the rewritten test.
david_chisnall | 16 hours ago
It's also not always a clear-cut thing. The hand-optimised version is not semantically identical, because it's now supporting closed-world types whereas the original was open-world. This is fine if you're doing whole-program optimisation and not loading plugins. LLVM can do this for C++, so probably could do the same for Rust.
But the real win comes from that conversion: it's a closed world, which means the call site is statically provably polymorphic not megamorphic. And that composes with the fact that all of the implementations are 3-4 instructions, so inlining is a clear win. Especially once you realise that CSE will unify the rectangle and triangle implementations, so you actually end up with something like two branches in the final version, possibly even one branch and a conditional move. Something like (C-like pseudocode):
The initial check is a branch because most architectures don't have predicated loads (you could make this faster if you had a non-trapping load, otherwise the load of the second field may trap so has to be hidden behind a branch).
But the fact that this is slower for this specific example is misleading. It's not removing the dynamic dispatch at execution time that makes it fast, it's the subsequent optimisation. If you want to preserve the original semantics, then other implementations may be faster.
There is a good argument to be made that a source language can be faster if it doesn't mandate any of these implementation choices and, ideally, conveys enough information to allow the compiler to choose the right one. Implementations of Smalltalk-family languages typically do this via profiling, but that may not show up in such a small benchmark.
Wilfred | 17 hours ago
Agreed, it looks like the C code is allocating on the heap and has a vtable, so
Box<dyn Shape>would be a fair comparison.https://github.com/richiemcilroy/Tov/blob/c2048582de4e9468267f801313144d75c12e983f/bench/micro/dispatch/main.c#L23-L24
Maybe the C compiler is optimising this better somehow?
aw1621107 | 15 hours ago
At least based on a quick glance in Godbolt (C, Rust) the dispatch loops look pretty similar.
C:
Rust:
For what it's worth the C and Rust variants in the folder you linked also perform pretty similarly on my machine as well.
wink | 19 hours ago
You can call me a bad amateur Rust programmer, but I didn't know about
ahashbecausestd::collections::HashMaphas been fine for me since I started writing Rust.That's kinda the only part where I am not fully on board with the assessment. Quoting from the docs "While its performance is very competitive for medium sized keys, other hashing algorithms will outperform it for small keys such as integers as well as large keys such as long strings, though those algorithms will typically not protect against attacks such as HashDoS" - this does not read "omg it's slow" to me. But looking at the benchmark, it still seems ok.
nrposner | 19 hours ago
For most real-world use cases, the standard hashmap is plenty fast. But when your application is meaningfully bottlenecked by hashing, or when you have a benchmark solely testing map insertions, it quickly becomes a test of the hash algorithm, rather than the surrounding language. Though the authors here don’t mention what hashing algorithm tov/typescript uses and whether it is intended to be cryptographically secure, which I think would be worth mentioning for completeness.
wink | 18 hours ago
Yeah exactly. It does different things but probably could have been chosen better or documented better. I'm a bit confused why a 2nd (fast) one would only be on crates, not in std, but I guess this being the default is ok.
nrposner | 18 hours ago
The standard library authors generally try to keep it small and lean on the crate ecosystem for non-default options. In the case of hashes, they probably wanted to keep a single, cryptographically secure default option, and anyone who wants to opt into a less secure option does it explicitly and intentionally by going to the crates ecosystem or writing their own, rather than choosing a less secure option from std.
snej | 17 hours ago
To be clear, it’s not HashMap that’s slow[ish], it’s the default hash function (SipHash). IIRC HashMap uses a state of the art hash table algorithm (is it SwissTable?)
natkr | 17 hours ago
In fact,
AHashMapis just std'sHashMapwith a different default hasher.rtfeldman | 17 hours ago
It is! Originally there was a crate called hashbrown - https://docs.rs/hashbrown/latest/hashbrown/ - that was a drop-in SwissTable replacement for std's HashMap, and then in 2019, Rust 1.36.0 adopted hashbrown's implementation as the new std HashMap: https://blog.rust-lang.org/2019/07/04/Rust-1.36.0/#a-new-hashmap-k-v-implementation
val | 15 hours ago
I use
HashSet<u64, rapidhash::RapidHasher>in a bunch of hot loops (eg. set of visited nodes in a Breadth-First Search). Even with the extra restriction to keys <= 50B it's really hard to beat with custom structures.The best I came up, besides bit vectors, with is using
Vec<HashSet<u32, rapidhash::RapidHasher>>by storing each valuenasn % (1<< 21)in the(n >> 21)th bucket (I have no idea why 21 gives the best perf). it saves half the memory (because we only store a u32 per value) but performance-wise it's only 5% faster.Right now, 30% of the runtime of a multi-day script is spent in
contains():(wink | 17 hours ago
You are right, I guess, but that's picking on a maybe vague phrase I used. If the user talks about "the HashMap (implementation)" then it would not work without a hash table algorithm, so I was talking about the whole thing. I had understood that, thanks for clarifying though.
yokljo | 19 hours ago
Yes. People often misunderstand the goals of Rust/C/C++/etc: They give you as many tools as possible to achieve bare metal performance, available to be used whenever they are needed. All that extra stuff kinda piles up and makes people confused.
Languages like Tov just try to make common use cases as fast as possible, but as soon as you leave that space, you soon run out of official tools to optimise things with and you end up working against the language. NGL it's super fun optimising things in spite of the tooling, but just not at work.