Big-O is one thing. Big constant factor, heap fragmentation and cache locality are other useful characteristics of data structures.
As far as constant factors go, this library is a middle ground; they strive for low constant factors in their algorithms, but it relies almost entirely on generic functions, so that alone is going to limit the maximum speed in e.g. tight loops.