New Rust hash table leads Benchmarks Game

UPDATE: Pushed a commit to my latest PR to replace the unsafe `File::from_raw_fd` with your `File::open`. Thanks!

https://github.com/mbrubeck/benchmarksgame-rs/blob/reverse_c...

It's very easy to write extremely fast safe Rust code. (The safe Rust version above is faster than the fastest C++ submission, on my computer.) Using "unsafe" for optimization is usually only helpful to get a few extra percent speedup in an inner loop. If this were production code rather than the benchmarks game, I'd probably ship the safe version.

> Experimental hash table implementation in just Rust (stable, no unsafe code).

https://github.com/bluss/ordermap

Before I left the Smalltalk part of my career behind, someone had the occasion to compare the parser-compiler of one Smalltalk which was implemented in C with Yacc/Lex with one implemented in pure Smalltalk with a JIT VM. IT turns out, once the console logging was disabled, the JIT VM's parser was just as fast as the one in C.

In my experience of almost 2 decades, it has been a constant that uninformed programmers are especially uninformed about the relative performance of managed languages.

Yeah, I wrote several published games entirely in assembly back when that was really the only reasonable option.

Of course some of the things we had to deal with meant that even the compilers were good, they couldn't have been good enough.

Extreme limited memory is the obvious one, but pages that need to be swapped out at runtime is the other one. An example: The Game Boy had 64k of memory addressing, but would ship with 128k and larger cartridges. 32k of the memory space was reserved for video memory, RAM, and hardware registers (if I remember correctly). The first 16k of memory was always mapped to the first 16k of ROM, but the second 16k of memory was mapped to arbitrary 16k blocks of ROM. 16k wasn't enough space to hold your entire game, so some code would leak into other pages (hopefully not more than ONE other page), but you also had to be able to swap other ROM pages into that second 16k memory region to, e.g., load graphics and game data.

There isn't a compiler around even today that can juggle all of that automatically. At a minimum you'd need to be marking different functions as belonging to different memory regions, but you'd still have to manually keep track of which function was where and ensure you don't try to call a region-2 function from a region-1 function when region-2 is some arbitrary ROM page instead of the extra code page. But often something in region-2 needs to call region-1 to load graphics into sprite registers and then restore region-2 so that the stack frame becomes valid again. :)

And 32k is SUCH a small amount of memory that being able to chip away at every single function was important. You have a function that does two things, but sometimes you just need to do the second? Put a label halfway through and call directly into the middle. You can save a byte here by loading one register into another, because you know that the registers will have the right values? Or you can save another byte there because you've realized that a particular constant is loaded a lot, and you can store that constant into one of the 128 cheap-memory locations? Do it! We need every byte...

Yes it would be possible to write such a compiler, but the level of effort to customize it to the specific architecture would be extreme. Easier to just make programmers do the hard work.

binary-tree is not useful for comparing GCed and non-GCed languages. For non-GCed languages, you are allowed to use a memory pool of your choice (the C version uses the Apache Portable Runtime library), for GCed languages you are required to use the standard GC with the default settings (no adjustment of GC parameters permitted). This is apples and oranges.

For mandelbrot, the C version uses handcoded SIMD intrinsics. I.e. it's not even portable to non-x86 processors.

It's also worth remembering that this is just a game, and as such it's somewhat of an apples-to-oranges comparison. Java's RAM usage may not be impressive compared to C, but that doesn't make the results overall any less impressive, especially knowing what it was like before those 20+ years of effort.

I don't see a reason that both Rust and Java's results can't be impressive in their own right. Java's numbers are (for the most part) impressive compared to C and Rust's numbers are also impressive compared to C, just in a different way.

Long ago the Ada program contributors told me -- It's only the same program if the same assembler is generated ;-)

Actually it's pretty easy: if you can write a faster version in any language, given whatever is there in the language, even if it's c implemented standard library stuff, do it.

The implementations are not meant to be final -- people can contribute faster ones.

FFI is a fact of life. I can imagine it would be perverting the intent of the game if you explicitly used FFI to delegate the actual core of the benchmark program to C as opposed to using "standard" building blocks, but the distinciton is necessarily vague.

1. Cache performance and locality may differ considerably for large applications. For example, a microbenchmark may perform well because it can monopolize the L1 cache in a way that is not possible for larger applications.

2. Aggressive inlining, a common factor in microbenchmark performance, may not scale well for large code bases. The tradeoffs here can be rather complex: https://webkit.org/blog/2826/unusual-speed-boost-size-matter...

3. Microbenchmarks often avoid abstraction in order to achieve high performance. This can create unacceptable software engineering costs.

EDIT, Nevermind Felix compiles to C++ and Pony looks like an academic project. If you want to provide benchmarks or try to change my mind, I am open to it, but it would require significant evidence.

I am not lamenting that someone should spend more time on this: I am lamenting that tons of people seem to care about it at all, it is not a "microbenchmark" (as some are calling it), and I think the main lesson we can learn from it is "there is something subtely wrong, either with the implementation that was contributed for this benchmark, the language's runtime, or it's standard library", as given these rules we really should expect every language to be similarly in performance.

And so, if we all cared about this benchmark, I bet we could figure out what is going on and get every open source language down under 25s. Past that point, I think the rules are such that this isn't even a fun game much less a useful metric of anything worth measuring, and you are probably wasting your time contributing. I guess, to make this subthread go somewhere: why do you disagree?

Though that's also an open addressed map.

Do the other programs use that same hash table algorithm?

http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul...

I think an adaptive hash that switches from fast to secure when collisions are detected would make a better default choice (at the cost of some implementation complexity).

Or possibly even an implementation with log(n) worst case complexity.

http://science.raphael.poss.name/rust-for-functional-program...

This post was a total revelation to me, even if I assume it's well known in the community, because it is very credible on the Sophie's Choice issue of mathematical purity versus acknowledgement of the reality of the instruction pointer-based imperative machine that exists underneath.

I've looked at other languages that "do" multiprocessing recently. Go is great, but it's essentially about getting large teams of variable-skill people to work together well. It's not an inspiring language, whereas Rust clearly is. Erlang (via Elixir) is very interesting, but the actor model will never be as performant in reality as the shared memory architecture. Julia is just a modern interpretation of matlab. A number of the JVM languages are great, but the "culture" of that ecosystem will always be corporate.

This is why I believe the science crowd could really gravitate to Rust, because it may have the ability, like the functional crowd, to satisfy the "search for beauty" aspect which motivates many academics, scientists, and indeed, programmers, all the while staying just the right side of pragmatism. And clearly targeting "where the puck is going" on massively multicore hardware.

The trial-and-error nature of scientific/data science discovery inevitably requires a REPL. If I had the right compiler/interpreter skills I would gladly contribute to making a Rust REPL happen. Unfortunately I don't. As it stands, all I can say is that if the REPL happens, I would be axed to contribute on the Rust scientific ecosystem with great motivation and pleasure.

318% is 20% bigger then 265%.