4 ms·
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 p
by ncmncm 7y ago
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.
- wjakob 7y agoWhat's wrong with red-black trees? :) Since you mention C++: you do realize that std::map will typically be implemented with one?
- _wldu 7y agostd::set too, which really is just a map where the key and value are the same.
- fluffything 7y agoHorrible cache utilization.
- The_rationalist 7y agoCompared to what?
- Polyisoprene 7y agoI believe Splay trees are usually mentioned as an alternative.
- cesarb 7y agoAren'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.)
- Polyisoprene 7y agoYeah, 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.
- alexhutcheson 7y agoIf 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.
- rrss 7y agoSeems 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.
- alexhutcheson 7y agoIMO "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.
- ComputerGuru 7y agoEven 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-tree/ https://neosmart.net/blog/2019/sorted-list-vs-binary-search-...
- alexhutcheson 7y agoThat's a good point, and a really interesting blog post.
- fluffything 7y agoA B-tree set, for example.
- wolf550e 7y agoYou 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.
- wahern 7y agoThe 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.
- alexhutcheson 7y agostd::map and std::set are famously terrible, for that reason: https://youtu.be/fHNmRkzxHWs?t=2695 https://youtu.be/fHNmRkzxHWs?t=2695
- ncmncm 7y agoIndeed. 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.
- floatboth 7y agoNetflix 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
- sesuximo 7y agothe 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
- snaky 7y agoUniversal 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?
- dooglius 7y agoUserspace libraries (which userspace programs could choose to use or not) would presumably be available.
- pnako 7y agoThat'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.
- snaky 7y agoIt 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 https://arxiv.org/abs/1909.07166
- snaky 7y agoOTOH, "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 https://arxiv.org/abs/1903.04075
- sitkack 7y agoWhat are your thoughts on DragonFlyBSD? https://www.dragonflybsd.org/ https://www.dragonflybsd.org/
- ncmncm 7y agoDon'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.
- asveikau 7y ago> 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.
- sitkack 7y agoSome of this might be possible with Dune, iommu or pointer tracking semantics. http://www.scs.stanford.edu/~dm/home/papers/belay:dune.pdf 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?
- ncmncm 7y agoI 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.
- jeffatfreebsd 7y agoWe 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.