The post discusses the use of a linked list in a Rust library for data validation, specifically in the context of JSON Schema. It explores various optimization ideas to improve the library's performance, including using alternative data structures, reusing memory allocations, and reducing struct sizes. The linked list implementation achieves a significant performance improvement, with approximately 4.5x improvement for valid inputs and 2.2x improvement for invalid inputs, compared to the naive approach.
Table of contents
Validation APIBenchmark setupNaive approachIdea 1: Cheaper clonesIdea 2: Reuse allocationsIdea 3: Linked listIdea 4: Precise memory allocationIdea 5: Avoid temporary VecIdea 6: Struct size optimizationMore ideas that didn't make itBonus idea: Maybe you don't need a linked list?Conclusion199 Impressions