I don't think PolyVox is slow, there's just some parts we'd like to make even faster
But yes, data structures do play a part in this. In the case of the LargeVolume and the A* implementation the idea was to get it working first, and then polish the implementation details later. Both of these may benefit from either a different standard container (hash_map over map for example) or from custom containers. The MeshDecimator on the other hand needs a completely different approach (in progress
here and
here).
Anyway, that LLVM stuff looks intersting as I wasn't really aware of that project. Some interresting static analysis stuff too.