Our great sponsors
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
Redis
Redis is an in-memory database that persists on disk. The data model is key-value, but many different kind of values are supported: Strings, Lists, Sets, Sorted Sets, Hashes, Streams, HyperLogLogs, Bitmaps.
-
-
mu
Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society. (by akkartik)
-
Once LLVM fixes some bugs with `noalias`, at which point Rust will begin using it again [1], I'd expect to see Rust get significantly faster in these benchmarks, given that the Rust compiler knows much more about which pointers do/do-not alias than most other programming languages [2] and the myriad optimizations this knowledge allows.
[1] https://github.com/rust-lang/rust/issues/54878#issuecomment-...
[2] https://doc.rust-lang.org/nomicon/aliasing.html
> I have no idea whether that matters or even easy to measure...
It is reasonably easy to measure, and the GP is about right. I've measured a crossover point of around a few hundred items too. (Though I'm sure it'll vary depending on use case and whatnot.)
I made a rope data structure a few years ago in C. Its a fancy string data structure which supports inserts and deletes of characters at arbitrary offsets. (Designed for text editors). The implementation uses a skip list (which performs similarly to a b-tree). At every node we store an array of characters. To insert or delete, we traverse the structure to find the node at the requested offset, then (usually) memmove a bunch of characters at that node.
Q: How large should that per-node array be? A small number would put more burden on the skip list structure and the allocator, and incur more cache misses. A large number will be linearly slower because of all the time spent in memmove.
Benchmarking shows the ideal number is in the ballpark of 100-200, depending on CPU and some specifics of the benchmark itself. Cache misses are extremely expensive. Storing only a single character at each node (like the SGI C++ rope structure does) makes it run several times slower. (!!)
Code: https://github.com/josephg/librope
This is the constant to change if you want to experiment yourself:
https://github.com/josephg/librope/blob/81e1938e45561b0856d4...
In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that.
One of my long standing complaints about modern programming is how rarely people read code. We don't encourage it in school, and in the workplace most people only read code written by their coworkers.
It would be the equivalent of teaching people to write books without encouraging them to read anything.
To break myself of the habit I started reading some well regarded programs for fun. And oh boy, have I learned a lot from doing so. One of my first discoveries was this beauty in the Redis source code:
https://github.com/redis/redis/blob/3.0/src/sds.h
The idea is to have a string struct that stores its length and content. But the pointer passed around is a pointer to the (null terminated) contents field in the struct. The string is efficient for internal calls (the length can be queried by subtracting from the pointer). But the pointer is also an idiomatic null-terminated C string pointer, compatible with the standard library and everything else.
Dovecot is also a gem to read if anyone has time. The way it manages memory pools is delightful - and I'm sure much more performant than idiomatic rust. (That is, without reaching for arena allocator crates and alternate implementations of Box and Vec).
There's a translator for C99 to (unsafe) Rust: https://github.com/immunant/c2rust
So probably you can give me any C program and I'll be able to give you an equivalent Rust program. It'll probably perform about the same, too.
Also Unix. Syscalls return null-terminated strings all over the place. So any language running on Unix has to deal with null-terminated strings.
I know because I run a userland that uses length-prefixed strings as far as possible: https://github.com/akkartik/mu
Not really answering your questions, but regarding monomorphization, you can see a comparison of code size and compilation speed between printf, std::format and C++ iostream. The last one is monomophization, I believe.
https://github.com/fmtlib/fmt#compile-time-and-code-bloat