The true cost of linked lists · YKarroum
Linked lists are often overused in introductory algorithmics courses, due to a heavy focus on theorical complexities. Unfortunatly, in practice, computers are complex beasts. They don’t execute instructions sequentially 1 with the same cost 2. This means that a data structure with faster theorical complexities does not necessarily translate to a more efficient data structure in practice.
The true cost of linked lists · YKarroum Just another personal blog, where I write about python, c++ and other stuff. © 2024. All rights reserved. YKarroum The true cost of linked lists 30 May 2022 Linked lists are often overused in introductory algorithmics courses, due to a heavy focus on theorical complexities. Unfortunatly, in practice, computers are complex beasts. They don’t execute instructions sequentially 1 with the same cost 2 . This means that a data structure with faster theorical complexities does not necessarily translate to a more efficient data structure in practice
related reading
- How to Optimize a CUDA Matmul Kernel for cuBLAS-like Performance: a Worklogsiboehm.com
- Making Deep Learning go Brrrr From First Principleshorace.io
- ⭐️ Fast LLM Inference From Scratchandrewkchan.dev
- Static search trees: 40x faster than binary search · CuriousCodingcuriouscoding.nl
- Transformer Inference Arithmetic | kipply's blogkipp.ly
- abseil / Performance Hintsabseil.io
- Intrusive linked lists - Data structures in practicedata-structures-in-practice.com
- Introduction - Learning Rust With Entirely Too Many Linked Listsrust-unofficial.github.io
- Memory location matters for performancepythonspeed.com
- Time complexity of operations on built-in typesdocs.python.org
- Effortless Performance Improvements in C++ | Julien Jorge's Personal Websitejulien.jorge.st
- Linked list - Wikipediaen.wikipedia.org