4 ms·
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 on
by josephg 6y ago
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 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. (typedef char *sds;)
Dovecot is also a gem to read if you're looking for inspiration. 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).
- steveklabnik 6y agoWhat makes you think arenas are considered unidiomatic in Rust? They’re there to be used when appropriate!
- josephg 6y agoThey seem unidiomatic because you have to fight the standard library to use them. Using an arena means abandoning String, Vec, Box, std::collections, and so on. I have no problem doing that if I need to. But it feels like I'm fighting against the grain of rust more than I'd like.
- burnthrow 6y agoThis topic is of great interest to me, do you know if there is any related official or community documentation on using arena allocation (and the problems you mentioned) in Rust? I've only found https://doc.rust-lang.org/1.1.0/arena/index.html https://doc.rust-lang.org/1.1.0/arena/index.html
- steveklabnik 6y agoCrates like https://crates.io/crates/typed-arena https://crates.io/crates/typed-arena and https://github.com/fitzgen/bumpalo https://github.com/fitzgen/bumpalo are the way you do this in today’s Rust, but what he’s referring to is that types like String manage their own allocations and aren’t yet parameterizable by an allocator. So they’re not super easy to use together. In my experience most of the time you need arenas you’re using your own data structure anyway, but YMMV.
- burnthrow 6y agoThanks for linking those projects and for "yet", which led me to the pages below https://rust-lang.github.io/rfcs/1398-kinds-of-allocators.html https://rust-lang.github.io/rfcs/1398-kinds-of-allocators.ht... https://github.com/rust-lang/rust/issues/32838 https://github.com/rust-lang/rust/issues/32838 https://github.com/rust-lang/wg-allocators https://github.com/rust-lang/wg-allocators
- josephg 6y ago> In my experience most of the time you need arenas you’re using your own data structure anyway, but YMMV. That makes sense for video games. Recently I was goofing with cyrus-imap. I wanted to parse the emails out of an mbox file into JSON (JMAP). Parsing an email with cyrus currently does about 5-10k calls to malloc, but the objects are all extremely short lived - they just have to live long enough to parse and then convert to JSON. This is a perfect case for a bump allocator - I'd love to allocate all the parsed email fields into an arena and then clear the whole thing when we move on to the next message. Yes, Cyrus uses a ton of its own internal structs for emails, and they're littered with strings and vectors. (Eg for email headers, lists of email recipients, plain text / HTML message content, etc). Looks like bumpalo will do the job, since it implements its own Box, Vector and String. I understand why, but it seems jarring that I'd need to replace the data types in order to change out the allocator like this. I'm definitely keen for GAT landing if it means bumpalo and friends don't need to reinvent the world to be able to change the allocation strategy. Edit: Oooh Vec::new_in is in nightly! Exciting! https://doc.rust-lang.org/beta/std/vec/struct.Vec.html#method.new_in https://doc.rust-lang.org/beta/std/vec/struct.Vec.html#metho...
- zamalek 6y agoThis is one of the things that GATs will solve: it will be possible to have a pointer trait. It's a known language limitation, so you are trying to do the right thing.
- nicoburns 6y agoPer object custom allocators are coming soon! I believe Vec already has an implementation on nightly.
- erik_seaberg 6y agoCOM on Windows also promoted BSTR as a language-neutral type, which was a pointer to a null-terminated UTF-16 string (compatible with Win32 entry points, at least the Unicode versions) preceded in memory by its length.
- AmericanChopper 6y agoMy go to troubleshooting method for open source tools I use is to just read the code to figure out what it’s doing (if I can’t quickly figure it out from the documentation). I’ve certainly learnt a lot from doing it, and I’ve even written patches for tools written in all sorts of languages that I’d never used before. The first time I ever wrote Rust and Go code, I was patching bugs in open source projects that I needed to have fixed.
- mjg59 6y agoThis feels like a wrapper around an equivalent of the Linux container_of construct (https://radek.io/2012/11/10/magical-container_of-macro/ https://radek.io/2012/11/10/magical-container_of-macro/). I have no idea whether there's further prior art in that respect.
- jstrong 6y agodo you have any recommended entry points for reading dovecot's code? I opened it up on github and it's a very large library! thanks for any help you can provide.
- josephg 6y agoNope not really! It is large, but you don't need to understand the big picture. Explore! I'd either start at a query entry point, or find the email delivery path or something. Or skim through the files and see if anything catches your eye. Or invent a question for yourself - how does X work (for some X), and see if you can find that part of the code. Wherever you start, explore around a bit then go deep. See if you can understand for yourself how some small, interesting part works (by tracing out the various structs and function calls). Understanding how the whole program fits together is a separate skill - but don't worry too much about it. Personally I fell in love with the code in src/lib/memarea and mempool. The way dovecot handles memory pools is super clever. There's also lots of src/lib-X directories, and they're reasonably self contained if you want to skim that list and find something more focussed. If you haven't read much code before and dovecot feels too big and scary, start with something smaller. I can also recommend reading the sourcecode for git or the code for redis. Oh, and if you do, do yourself a favour and checkout one of the earlier versions of those projects. The lines added early in a project's life are usually more succinct and important compared to lines added later on. So earlier versions are usually better reads. When I read redis, I think I read the code for redis 2.0 or something.
- michaelmior 6y agoThey're somewhat old now, but I'd recommend checking out The Architecture of Open Source Applications series of books. https://aosabook.org/en/index.html https://aosabook.org/en/index.html