Ch4: dsal

What is dsal?

dsal stands for Data Structures and Algorithms. In the context of fast_io, this chapter introduces container implementations and algorithmic utilities that support the I/O system. While fast_io is primarily an input/output library, certain features require efficient data structures to function correctly.

Why does an I/O library have containers?

Initially, containers were deliberately avoided in fast_io to keep the library focused purely on I/O. However, some I/O features cannot be implemented without them. For example:

• File system traversal: Recursive iteration requires a stack or similar container to store directory entries.
• Locale system: Implementing a locale system based on glibc metadata requires a map-like structure to manage character and formatting rules.

Without containers, these essential features would be impossible to provide.

Why not just use the C++ standard library?

The C++ standard containers are not freestanding, while fast_io is designed as a freestanding library. Standard containers rely on exceptions like std::logic_error, which are unnecessary here. Instead, fast_io prefers to use __builtin_trap to terminate on programming bugs, ensuring safer and faster semantics.

Other limitations of the standard library include:

• Inefficient allocator design: std::allocator<T> duplicates code unnecessarily for types of the same size, preventing debloating optimizations.
• Problematic polymorphic memory resources (pmr): These often introduce fragmentation and are rarely used in real-world code.
• Overuse of new and exceptions: fast_io avoids these, preferring fail-fast allocation strategies.
• Missing data structures: The standard library does not provide useful containers like B‑trees or string maps, which are essential for efficient I/O tasks.
• Flawed designs: std::list maintains a size() member, which adds overhead and defeats the purpose of using a linked list.

Unified Interface for I/O and Containers

One of the core goals of fast_io is to redesign both I/O and containers under a consistent interface. In traditional C++ libraries, I/O streams and containers often expose different semantics, error handling strategies, and allocation models. This inconsistency leads to subtle bugs and unnecessary complexity.

By aligning the design of containers with the same principles as I/O — fail-fast allocation, noexcept guarantees, and lean abstractions — we ensure that developers can reason about both systems in the same way. This reduces friction, avoids duplicated logic, and makes it easier to build robust applications.

• Containers and I/O streams share the same error handling philosophy (terminate on corruption or logic bugs).
• Allocators are unified, avoiding fragmentation and inefficiency.
• Interfaces are predictable, lowering the risk of misuse and subtle inconsistencies.

The result is a coherent ecosystem where I/O and data structures complement each other, rather than feeling like separate worlds stitched together.

The Philosophy

The guiding principle is that allocation failures and programming bugs should terminate immediately rather than attempt recovery. This approach has been validated in practice: Microsoft tested replacing std::bad_alloc with termination in critical software like Office, and found no noticeable increase in crashes. Similarly, modern operating systems like Android and iOS routinely kill background processes without user complaints.

In short, fast_io containers are designed to be lean, fail-fast, and optimization-friendly, aligning with the library’s overall philosophy of safe and efficient I/O.