Data Structures in Practice

Data Structures in Practice: A Hardware-Aware Guide for System Software Engineers

Data Structures in Practice offers an innovative exploration of data structures tailored specifically for system software engineers. This guide provides not only theoretical insights but also practical knowledge by examining how various data structures interact with hardware at a fundamental level.

What Sets This Book Apart

• Hardware-First Perspective: Each data structure is scrutinized through key concepts such as cache behavior, memory hierarchy, and CPU microarchitecture, providing a deeper understanding of performance implications.
• Real-World Benchmarks: The book features actual performance data derived from modern processors including RISC-V, ARM, and x86, enabling engineers to make informed decisions based on empirical evidence.
• Focus on System Software: Examples throughout the text are drawn from the realms of bootloaders, device drivers, firmware, and embedded systems, ensuring relevance to practical applications.
• Bilingual Availability: The text is accessible in both English and Traditional Chinese, broadening its reach to a wider audience.

Learning Outcomes

Readers will gain insights into key topics such as:

• The impact of cache misses on linked list performance.
• The significance of choosing between array-of-structures and structure-of-arrays in SIMD operations.
• The contextual appropriateness of B-trees versus hash tables in embedded systems.
• Techniques for accurate benchmarking and profiling of data structures.
• Understanding of lock-free data structures tailored for concurrent environments.
• In-depth analysis of memory allocator design and fragmentation.

Comprehensive Structure

The book is divided into distinct parts covering foundational concepts, basic data structures, trees and hierarchies, advanced topics, and case studies:

• Foundations (Chapters 1-3): Discusses the performance gap, memory hierarchy, and benchmarking.
• Basic Data Structures (Chapters 4-8): Explores arrays, linked lists, stacks, queues, hash tables, and dynamic arrays.
• Trees and Hierarchies (Chapters 9-12): Focuses on binary trees, B-trees, tries, and heaps.
• Advanced Topics (Chapters 13-16): Includes lock-free data structures, string processing, graphs, and probabilistic data structures.
• Case Studies (Chapters 17-20): Provides real-world applications from bootloaders, device drivers, and firmware.
• Appendices (A-F): Offers additional resources, exercises, and solutions.

Target Audience

This guide is designed for system software engineers, embedded systems developers, performance engineers, and computer science students who aspire to integrate hardware-awareness into their understanding of data structures. A foundational knowledge of C programming and memory principles is beneficial for readers.

Contribution Opportunities

Feedback is encouraged to enhance the quality of content. While this repository is read-only, constructive input regarding typos, errors, or suggestions is welcomed through issue submissions.

Read and Explore

Available source files in English and Traditional Chinese can be accessed directly within the repository. The comprehensive reading list guides readers sequentially through the chapters and supports an enriching learning experience.

Engagement in discussions and questions is encouraged, reflecting the collaborative spirit of the open-source community. This project appreciates the contributions of the RISC-V ecosystem and aims to foster a deeper understanding of data structures in relation to machine architecture.

For any inquiries or feedback, please connect via the repository’s issue tracker.