acidx

If I understood this comment correctly, this approach wouldn't work with a single possible tombstone value.

If the table has, for instance, a tophashes array that looks something like VVVVVVdVVVV, where "V" is any value, and "d" is a deleted item, you can't stop looking after the "d" value -- as your item might be there.

Yes! The JSON library I wrote for the Zephyr RTOS does this. Say, for instance, you have the following struct:

    struct SomeStruct {
        char *some_string;
        int some_number;
    };

You would need to declare a descriptor, linking each field to how it's spelled in the JSON (e.g. the some_string member could be "some-string" in the JSON), the byte offset from the beginning of the struct where the field is (using the offsetof() macro), and the type.

The parser is then able to go through the JSON, and initialize the struct directly, as if you had reflection in the language. It'll validate the types as well. All this without having to allocate a node type, perform copies, or things like that.

This approach has its limitations, but it's pretty efficient -- and safe!

Someone wrote a nice blog post about (and even a video) it a while back: https://blog.golioth.io/how-to-parse-json-data-in-zephyr/

The opposite is true, too -- you can use the same descriptor to serialize a struct back to JSON.

I've been maintaining it outside Zephyr for a while, although with different constraints (I'm not using it for an embedded system where memory is golden): https://github.com/lpereira/lwan/blob/master/src/samples/tec...

The Linux man page (https://man7.org/linux/man-pages/man3/atoi.3.html#VERSIONS) says that POSIX.1 leaves it unspecified. As you found out, it's really something that should be avoided as much as possible, because pretty much everywhere disagrees how it should behave, especially if you value portability.

sscanf() is not a good replacement either! It's better to use strtol() instead. Either do what Lwan does (https://github.com/lpereira/lwan/blob/master/src/lib/lwan-co...), or look (https://cvsweb.openbsd.org/src/lib/libc/stdlib/strtonum.c?re...) at how OpenBSD implemented strtonum(3).

For instance, if you try to parse a number that's preceded by a lot of spaces, sscanf() will take a long time going through it. I've been hit by that when fuzzing Lwan.

Even cURL is avoiding sscanf(): https://daniel.haxx.se/blog/2025/04/07/writing-c-for-curl/

One thing to note, too, is that `atoi()` should be avoided as much as possible. On error (parse error, overflow, etc), it has an unspecified return value (!), although most libcs will return 0, which can be just as bad in some scenarios.

Also not mentioned, is that atoi() can return a negative number -- which is then passed to malloc(), that takes a size_t, which is unsigned... which will make it become a very large number if a negative number is passed as its argument.

It's better to use strtol(), but even that is a bit tricky to use, because it doesn't touch errno when there's no error but you need to check errno to know if things like overflow happened, so you need to set errno to 0 before calling the function. The man page explains how to use it properly.

I think it would be a very interesting exercise for that web framework author to make its HTTP request parser go through a fuzz-tester; clang comes with one that's quite good and easy to use (https://llvm.org/docs/LibFuzzer.html), especially if used alongside address sanitizer or the undefined behavior sanitizer. Errors like the one I mentioned will most likely be found by a fuzzer really quickly. :)

Programs running under any Valgrind tool will be executed using a CPU emulator, making it quite a bit slower than, say, running the instrumented binaries as required by sanitizers; it's often an order of magnitude slower, but could be very well be close to two orders of magnitude slower in some cases. This also means that it just can't be attached to any running program, because, well, it's emulating a whole CPU to track everything it can.

(Valgrind using a CPU emulator allows for a lot of interesting things, such as also emulating cache behavior and whatnot; it may be slow and have other drawbacks -- it has to be updated every time the instruction set adds a new instruction for instance -- but it's able to do things that aren't usually possible otherwise precisely because it has a CPU emulator!)

Go has had its own version of msan and asan for years at this point.

I wrote the Lwan web server, which similarly to Go, has its own scheduler and makes use of stackful coroutines. I have spent quite a bit of time Valgrinding it after adding the necessary instrumentation to not make Valgrind freak out due to the stack pointer changing like crazy. Despite a lot of Valgrind's limitations due to the way it works, it has been instrumental to finding some subtle concurrency issues in the scheduler and vicinity.

From a quick glance, it seems that Go is now registering the stacks and emitting stack change commands on every goroutine context switch. This is most likely enough to make Valgrind happy with Go's scheduler.

I recently wrote one, in C, using tail calls to implement dispatch with CPS: https://tia.mat.br/posts/2025/08/30/forth-haiku.html

It's already pretty efficient but I'm working on it to make it even more efficient so I can use it as some sort of primitive fragment shader for an art project. This Forth variant is intended to execute Forth Haikus, as defined by the Forth Salon website.

I recently implemented a Forth, compatible with the Forth Haiku dialect used by https://forthsalon.appspot.com/ -- it uses a tail call/continuation-passing dispatching method, and performs some rudimentary optimizations. At some point it also spit out some C but I decided to give this feature the axe until it has a better infrastructure for optimizations and codegen.

The idea is to use it to drive an LED matrix and have a simple web UI to develop "fragment shaders" in Forth. It's developed as part of the Lwan project, although currently it generates GIF files on the fly rather than drive a LED matrix.

The source code is here for those that want to play with it: https://github.com/lpereira/lwan/tree/master/src/samples/for...

There's another small one in Campinas, near the Nipo-Brazilian Institute: https://viajantesemfim.com.br/rua-camargo-paes-um-pedacinho-... (or on GMaps: https://maps.app.goo.gl/P17sBzkNG3Gk4frq5)

I'm sure there are many, many more throughout the country, especially in the states of São Paulo and Paraná.

Also in Brazil: https://en.wikipedia.org/wiki/Nova_Iorque

Thank you!

Reminds me of this sample from the Lwan project: https://time.lwan.ws/blocks -- where the clock is rendered on the server, and new frames are sent to the client using chunked encoding.

Details are hazy as this was a long time ago, but at some point you could make parts of messages not render in Outlook and Outlook Express by writing "begin something" (two spaces after "begin") by itself in a single line. Outlook would thing that it was the start of an uuencoded block and not render anything after that.

I remember annoying friends in a mailing list by quoting emails with "begin quote from Person Name:" :)

This is roughly what my JSON parser does. It does type-checking, albeit without using JSON-schema, but an object descriptor that you have to define to parse and generate JSON.

It's been developed for embedded systems (it was written originally for a NATS implementation in the Zephyr RTOS), so it's a bit limited and there's no easy way to know where some parsing/type validation error happened, but the information is there if one wants to obtain it: https://github.com/lpereira/lwan/blob/master/src/samples/tec...

Yes, that's the library! It's something I've been slow cooking for over 10 years at this point. :)

It's collected after 15min, give or take. The hash isn't random, it's the SHA-1 hash of the base64-encoded data, so it's predictable -- if something keeps accessing the base-64 encoded URL, the /s/... URL won't vanish.

I tried making it more strict (by checking the Sec-Fetch-Site and Sec-Fetch-Dest headers), but not all browsers send that.

On the client.

Data is already stored in the ZIP file deflated, so I can just send whatever is inside the ZIP file back to the client if they accept that encoding (which is pretty much always the case, given how ubiquitous deflate is).

The server parses the ZIP file and stores that information in a hash table for quicker lookup but it's otherwise not decompressing anything. This hash table is kept for a few minutes to avoid having to decode the base64-encoded data and parse the ZIP file for every request.

I love this!

Then it would require JavaScript and wouldn't be a nice demonstration for my web server library. :)

Oh, this is a cool experiment!

That's why we can't have nice things. :(

Files are not decompressed in the server: it sends the unmodified deflate stream back to the user.

Lwan: https://lwan.ws

Been working on this for exactly 11 years today! It's just a webserver on the outside but it has become an umbrella for experimentation.

Lwan (https://lwan.ws) can also be used like this, although I wouldn't call it a "one liner" like many of the examples listed there:

    lwan -r /path/to/files/to/serve

Nice article and analysis! I'm actually considering scrapping the trie used in my project to something based off of this one, with some modifications:

For instance, find_node(c, Node48) could avoid the branch if a non-existing index points to an additional entry in child_ptrs that's always NULL. Lookup would be comparable to the Node256 version.

Another thing that could be done, is to scrap the Node48 entirely, and implement two new structs to replace it: Node32 and Node64, and use respectively AVX2 and AVX512. These can be based off of the Node16 version. It remains to be seen if these will yield better performance than the branchless Node48 above, especially if power management kicks in when mixing AVX512 with older SIMD generations.

The trie in Lwan (https://lwan.ws) does an interesting trick to reduce the amount of memory used in the equivalent of a Node256: instead of 256 pointers to a node, it has only 8 pointers. Characters are hashed (MOD 8). The leaf node contains a linked list of key/value pair, and an actual string comparison is performed at the end. (Lwan cheats here by avoiding a string comparison if the linked list contains only 1 element.) Works pretty well, as it's part of the URL routing mechanism.

One other experiment I've been making with tries, is to use the idea of key compression and use it in a different way: slice it every 4 or 8 bytes, consider those bytes as an arbitrary integer, and add every chunk of it to a hashmap<int, some_struct>, building a chain for the next lookup in some_struct. The prototype I wrote works pretty well.

I like this trick that I use in C. It's limited, as it only matches string prefixes, but it works pretty well in the end: https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in...

It allows you to write something like this: https://github.com/lpereira/lwan/blob/master/src/lib/lwan-ti... -- which is generated as a binary search by GCC.

No -- in Lwan, files that will be sent with sendfile() are kept open for a while; when they're first open, the same thread that opened (and this might block) will call readahead(). Files are sent in 512kB bursts. It might use mmap()+madvise(), but only for small files (<16KB)... but, yeah, there's not a lot of control here. I'm not that worried, though; this is but a toy. :)

Registered I/O (RIO) or I/O Completion Ports (IOCP) in Windows seems to be better in this regard, but I don't have a lot of experience in that platform. Trent Nelson, from the PyParallel project, has a few talks about it; it's quite neat.

Thanks!

I don't think there's a way to guarantee that sendfile() won't block on Linux. On FreeBSD, you can specify a "go as much as you can without blocking, and then return" flag; Linux doesn't have a flags parameter for sendfile() (maybe it needs a sendfile2() syscall with that?).

You can maybe use readahead() and keep the file open, but that may also block as it does its work behind the scenes. A thread just for this kind of blocking calls would be nice. But even then, this doesn't seem sufficient; so you might want to use multiplex sendfile() calls in bursts.

Also, yeah, Linux aio syscalls are interesting, but they're quite tricky to use and not very portable. I'll check out your project, thanks for linking to it -- should be useful reading material while I learn Rust.

I'm not aware of it. I'm learning Rust (just bought the "The Rust Programming Language" book, FWIW), so I will check it out.