Back Home

Table of Contents

Algorithms

Quickselect with Median of Medians considered practical: (Kurosawa 2016)

References

Kurosawa, Noriyuki. 2016. “Quicksort with Median of Medians Is Considered Practical,” August. https://doi.org/10.48550/arXiv.1608.04852.

A Linear time algorithm for quickselect

(Blum et al. 1973)

To read about quickselect: (Alexandrescu 2016)

Ipnsort: a new unstable sort – (Bergdoll and Peters 2024)

Changing std::sort (Kutenin 2022)

References

Alexandrescu, Andrei. 2016. “Fast Deterministic Selection.” https://arxiv.org/abs/1606.00484.
Bergdoll, Lukas, and Orson Peters. 2024. “Ipnsort: An Efficient, Generic and Robust Unstable Sort Implementation.” 2024. https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md.
Blum, Manuel, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. 1973. “Time Bounds for Selection.” Journal of Computer and System Sciences 7 (4): 448–61. https://doi.org/10.1016/S0022-0000(73)80033-9.
Kutenin, Danila. 2022. “Changing Std::sort at Google’s Scale and Beyond.” 2022. https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/.

Computer Architecture

Compiler misoptimizations: (Bernstein 2024)

To Save C, We must Save ABI: (Meneide 2022)

More ABI problems in C/C++: (Meneide 2021)

C is not a low-level language: (Chisnall 2018)

Optimizations in C++ compilers: (Godbolt 2019)

Something about LZMA (Ziv and Lempel 1977)

What you C is what you get (Simon, Chisnall, and Anderson 2018)

How to write an ISA – (Chisnall 2024)

Algorithms for modern hardware: (Slotin 2024)

Crash-only software: (Candea and Fox 2003)

References

Bernstein, Daniel J. 2024. “Clang Vs. Clang.” 2024. https://blog.cr.yp.to/20240803-clang.html.
Candea, George, and Armando Fox. 2003. “Crash-Only Software,” May. https://www.usenix.org/conference/hotos-ix/crash-only-software.
Chisnall, David. 2018. “C Is Not a Low-Level Language: Your Computer Is Not a Fast PDP-11.” Queue 16 (2): 18–30. https://doi.org/10.1145/3212477.3212479.
———. 2024. “How to Design an ISA.” Commun. ACM 67 (5): 60–66. https://doi.org/10.1145/3640538.
Godbolt, Matt. 2019. “Optimizations in c++ Compilers: A Practical Journey.” Queue 17 (5): 69–100. https://doi.org/10.1145/3371595.3372264.
Meneide, JeanHeyd. 2021. “Binary Banshees and Digital Demons.” 2021. https://thephd.dev/binary-banshees-digital-demons-abi-c-c++-help-me-god-please.
———. 2022. “To Save c, We Must Save ABI.” 2022. https://thephd.dev/to-save-c-we-must-save-abi-fixing-c-function-abi.
Simon, Laurent, David Chisnall, and Ross Anderson. 2018. “What You Get Is What You c: Controlling Side Effects in Mainstream c Compilers,” 1–15. https://doi.org/10.1109/EuroSP.2018.00009.
Slotin, Sergey. 2024. “Algorithms for Modern Hardware.” 2024. https://en.algorithmica.org/hpc/.
Ziv, J., and A. Lempel. 1977. “A Universal Algorithm for Sequential Data Compression.” IEEE Transactions on Information Theory 23 (3): 337–43. https://doi.org/10.1109/TIT.1977.1055714.

Networking

Development of the Domain Name System: (Mockapetris and Dunlap 1988)

A protocol for packet network intercommunication (TCP/IP): (Cerf and Kahn 1974)

For more notes about the C ABI

References

Cerf, Vint, and Bob Kahn. 1974. “A Protocol for Packet Network Intercommunication.” IEEE Transactions on Communications 22 (5): 637–48. https://doi.org/10.1109/TCOM.1974.1092259.
Mockapetris, P., and K. J. Dunlap. 1988. “Development of the Domain Name System.” SIGCOMM Comput. Commun. Rev. 18 (4): 123–33. https://doi.org/10.1145/52325.52338.

VMs

Firecracker: (Agache et al. 2020)

References

Agache, Alexandru, Marc Brooker, Andreea Florescu, Alexandra Iordache, Anthony Liguori, Rolf Neugebauer, Phil Piwonka, and Diana-Maria Popa. 2020. “Firecracker: Lightweight Virtualization for Serverless Applications.” https://www.amazon.science/publications/firecracker-lightweight-virtualization-for-serverless-applications.

Historical

Reflections on Trusting Trust: (Thompson 1984)

Three approaches to the quantitative definition of information (Kolmogorov 1968)

References

Kolmogorov, A. N. 1968. “Three Approaches to the Quantitative Definition of Information *.” International Journal of Computer Mathematics 2 (1-4): 157–68. https://doi.org/10.1080/00207166808803030.
Thompson, Ken. 1984. “Reflections on Trusting Trust.” Commun. ACM 27 (8): 761–63. https://doi.org/10.1145/358198.358210.
View history for this file: on Github