Using a linked-list where the actual access pattern is random and an hash table is more suitable would be the most obvious, especially since this is C code. Si

Using a linked-list where the actual access pattern is random and an hash table is more suitable would be the most obvious, especially since this is C code. Similar things includes C-style string functions like strlen() and so on that require iterating over an unknown length array. Caching (or better avoiding!) this work can save a lot of computing time. Example from libgit2: https://github.com/libgit2/libgit2/commit/7132150ddf7a883c1f12a89c2518c1a07c0dc94c https://github.com/libgit2/libgit2/commit/7132150ddf7a883c1f... In fact C-style string is a rich source of O(n) performance issues. And git is full of strings like filenames.