Hacker News Reader

Comment by ncmncm | Hacker News Reader

FreeBSD could get a boost by switching to building with a C++ compiler, beginning to modernize their ancient codebase (red-black trees, really?), and inviting people with modern ideas to implement them.

The exokernel people know how to write good kernel-grade C++. Much of the code just needs to go; kernels can't keep up with the I/O needs of user-space programs, and need to learn to get out of the way. Linux has its io_uring thing which is vastly overcomplicated. FreeBSD could lead the way with universal kernel bypass, with only authentication, resource allocation, and permissions handled in ring zero.

Much more likely, though, is that somebody new will need to start from scratch.

View on HN

What's wrong with red-black trees? :) Since you mention C++: you do realize that std::map will typically be implemented with one?

Horrible cache utilization.

Compared to what?

I believe Splay trees are usually mentioned as an alternative.

Aren't splay trees terrible because they turn all reads into writes? (Which means the cache lines bounce between readers, instead of being shared as they would be with pure reads.)

Yeah, having reads rebalancing the tree in a multithreaded subsystem is probably not optimal. Might be that the Splay-trees have outstayed their welcome :)

FreeBSD’s tree.h used to have, iirc, both RB- and Splay-trees.

If you're not interleaving insertions and lookups, then a sorted vector can be really good.

If you need to interleave insertions and lookups, but don't need to traverse in sorted order, then a good hash table (not std::unordered_map) is normally the best option.

You only need a tree if you need traversal in sorted order and interleaved insertions and lookups, which is pretty uncommon. Even then you are almost always better off with a B-tree than a red-black tree.

Seems like these criteria miss the use case for mm_rb, one of the central red-black trees in linux.

If you need to be able to store intervals (i.e. virtual memory areas) and do lookups based on any address in the interval, not just the base address, I don't think a hash map is the best option.

IMO "lookups based on any address in the interval" requires "traversal in sorted order", although I could have probably been more precise in my terms.

I would be curious if anyone has ever profiled the impact of changing mm_rb to a B-tree. It might be very difficult if existing code that uses mm_rb depends on pointer stability, though.

Even with interleaved insertions and lookups, there are common scenarios that make a sorted vector still significantly more performant. I wrote about it when we published our open source SortedList<T> implementation for .NET and .NET Core [0], specifically comparing it to AVL and Red-Black trees.

[0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-...

That's a good point, and a really interesting blog post.

A B-tree set, for example.

std::set too, which really is just a map where the key and value are the same.

You want more fanout to use the entire cache line or even the entire virtual memory page. RB trees assume access to any address in memory has equal cost, which is extremely incorrect.

The red-black tree implementation typically used in *BSD development, <sys/tree.h>, is an intrusive data structure; tree nodes are embedded within the object you must dereference for key comparison. There's no need to optimize fanout because you've entirely removed that extra indirection.

As a general purpose data structure implementation for systems development, <sys/tree.h> is quite nice. However, for any particular task you can always optimize the data structure, or choose an entirely different data structure, to better fit the problem. Which is perhaps why the Linux kernel has so many different tree and hash implementations.

std::map and std::set are famously terrible, for that reason: https://youtu.be/fHNmRkzxHWs?t=2695

Indeed. C++ needs some better Standard containers. As it is, you need 3rd party library containers when you need optimal performance on ordered collections. Abseil and boost have alternatives.

The great advantage C++ has is that there is no temptation to open-code them. Library implementations can absorb immense optimization and testing effort, amortized over all uses, and delivered without compromise.

Netflix went in the opposite direction and contributed KTLS so we now have encrypted sendfile :)

but we also have netmap, which is like mmap for networking, pretty cool stuff

the http related syscalls in freebsd are so nice to work with. it's a small thing but it makes me happy whenever I get to use it

We have quite a few types of trees that are available in generic implementations. red black is not even commonly used. The vm has had a path compressed radix tree for over a decade. We had more splay than red back really.

Universal kernel bypass for IO? Does it imply every userspace program should know how to communicate with every kind of IO device? No block layer? What about memory and caching?

Userspace libraries (which userspace programs could choose to use or not) would presumably be available.

That's not a bad idea. You'll need some sort of mechanism to make sure they don't step on each other's toes, but otherwise it's a sound concept, not unlike MS-DOS.

It seems some highest-performant enterprise solutions consider the MS-DOS way as well.

"The Coherent Accelerator Processor Interface (CAPI) is a general term for the infrastructure that provides high throughput and low latency path to the flash storage connected to the IBM POWER 8+ System. CAPI accelerator card is attached coherently as a peer to the Power8+ processor. This removes the overhead and complexity of the IO subsystem and allows the accelerator to operate as part of an application. In this paper, we present the results of experiments on IBM FlashSystem900 (FS900) with CAPI accelerator card using the "CAPI-Flash IBM Data Engine for NoSQL Software" Library. This library provides the application, a direct access to the underlying flash storage through user space APIs, to manage and access the data in flash. This offloads kernel IO driver functionality to dedicated CAPI FPGA accelerator hardware. The results indicate that FS900 & CAPI, together with the metadata cache in RAM, delivers the highest IO/s and OP/s for read operations. This was higher than just using RAM, along with utilizing lesser CPU resources."

https://arxiv.org/abs/1909.07166

OTOH, "As one step toward building high performance NVM systems, we explore the potential dependencies between system call performance and major hardware components (e.g., CPU, memory, storage) under typical user cases (e.g., software compilation, installation, web browser, office suite) in this paper. We find that there is a strong dependency between the system call performance and the CPU architecture. On the other hand, the type of persistent storage plays a less important role in affecting the performance."

https://arxiv.org/abs/1903.04075

What are your thoughts on DragonFlyBSD?

https://www.dragonflybsd.org/

Don't know much about it, other than that it has a version of variable expansion in symlinks that I liked on Apollo's Aegis, then Domain/OS, back in the day.

Aegis had a better read() syscall than Unix. You would give it a buffer, but it would return a pointer into its buffer cache if it could, and only copy to your buffer if not.

> Aegis had a better read() syscall than Unix. You would give it a buffer, but it would return a pointer into its buffer cache if it could, and only copy to your buffer if not.

You could do a similar hack with a Unix interface. Eg. the syscall could change the page table so that the caller's buffer now points to a COW page in buffer cache. Worst case you would need to copy 2*(PAGE_SIZE-1) bytes that are not page aligned.

This also has me wondering... If the kernel is handing out pointers to cache, it would need to do some MMU protections too, right? So the costs of COW pages would still likely need to be incurred with a "better" interface.

Some of this might be possible with Dune, iommu or pointer tracking semantics.

http://www.scs.stanford.edu/~dm/home/papers/belay:dune.pdf

I had never heard of Aegis, how big is my blindspot and what do you recommend?

I gather that Aegis took its inpiration from Multics, which I have not studied, but is said to rely very heavily on memory mapping. Aegis ran on custom bit-slice re-implementations of the 68000, and later on 68020s. It mapped all the system libraries, shared, to the same address of all processes because the 68000 was bad at position-independent code. It integrated a token-ring network, and demand-paged over the network, in the early '80s. You could fork onto any machine on the ring. It was very advanced for its time. Some of its best features are not seen on current systems.

> You could fork onto any machine on the ring. It was very advanced for its time.

So a precursor to research operating systems like Mosix, Amoeba and Sprite. The Mosix literature doesn't mention it, but I think it is/was common to not mention work in industry. This is really cool, every time I dive into old research there is always something mind opening.

afaik, the 68k was actually good are PIC code, it just didn't have any memory protection until the 68020. On pages 2-13 through 2-17 of the 68k programmer's reference manual it outlines the program counter relative addressing modes.

https://www.nxp.com/files-static/archives/doc/ref_manual/M68...

Dune looks very, very interesting. Thank you for the reference.

Reply on news.ycombinator.com