5 ms·

Another name for that is "B* tree". Or anyway a thing with similar performance characteristics.

kabdib 4y ago
Right, though we didn't need full tree semantics (just fast random access and an append that didn't spool up the fans on the servers). I would hate to have to do a full balanced b-tree on short notice. (We also had rather terrible extra requirements that made using an off-the-shelf thing from, say, the STL work in our environment).
- dilap 4y ago
  simple vector implementations will do a full realloc and recopy when you run out of space. so O(1) amortized but O(N) every so often. another implementation strategy, at the cost of using some extra memory, is to allocate the new space, but only copy over a bit at a time, each time a new element is added -- so every add is still O(1). no long pauses. (well, assuming the memory alloc is still fast. which i think it should be in practice? tho i'm not super familiar w/ that stuff.) just curious, do you think that solution would have worked for your situation too?
  - kabdib 4y ago
    That's exactly the strategy that was tipping over. Once you start resizing vectors of tens of megabytes, it's kind of over. You can start playing games by accelerating capacity allocation when a vector rapidly starts growing extremely large. This doesn't solve the problem that vectors sometimes guarantee too much for what you need.
    - dilap 4y ago
      Ah thanks, I didn't read closely enough the first time.
- samsquire 4y ago
  For a simple and readable implementation of a Python btree see this: https://github.com/samsquire/btree https://github.com/samsquire/btree I tried to keep the implementation as simple as I could.
cobalt 4y ago
also what a deque (C++) does
- pencilguin 4y ago
  True... except in MSVC. std::deque in MSVC is cursed. Targeting MSVC, use boost::deque or something, instead. Boost containers are generally fairly good, although they are more or less unmaintained nowadays. (E.g., boost::unordered_map::reserve doesn't work.) Or, like many of us, ignore performance on MS targets because anybody who cares about performances is running something else.
  - q-big 4y ago
    Why?
    - pencilguin 4y ago
      https://github.com/AcademySoftwareFoundation/openvdb/issues/1350 https://github.com/AcademySoftwareFoundation/openvdb/issues/... Longer answer is that the size of the "blocks" is limited to 512 bytes or one element, whichever is larger. So unless your elements are really tiny, it is strictly a pessimization.
  - cyber_kinetist 4y ago
    Many of the STL containers in MSVC are incredibly cursed. Even std::vector is implemented in such a weird way, that you can't debug it easily with any debugger other than Visual Studio. And it's incredibly slow on Debug mode, up to the point that it's unusable... (Because of these reasons I just switched to using my own Vector<T> class recently) I think there's a very good reason why old gamedevs who were stuck with developing on Windows largely ignored the STL and made their own containers / utility functions: MSVC's STL was just awful.
    - brantonb 4y ago
      I always wondered why we weren’t allowed to use the STL in the Windows division in the 00’s. This probably explains it.

Right, though we didn't need full tree semantics (just fast random access and an append that didn't spool up the fans on the servers). I would hate to have to do a full balanced b-tree on short notice. (We also had rather terrible extra requirements that made using an off-the-shelf thing from, say, the STL work in our environment).

dilap 4y ago
simple vector implementations will do a full realloc and recopy when you run out of space. so O(1) amortized but O(N) every so often. another implementation strategy, at the cost of using some extra memory, is to allocate the new space, but only copy over a bit at a time, each time a new element is added -- so every add is still O(1). no long pauses. (well, assuming the memory alloc is still fast. which i think it should be in practice? tho i'm not super familiar w/ that stuff.) just curious, do you think that solution would have worked for your situation too?
- kabdib 4y ago
  That's exactly the strategy that was tipping over. Once you start resizing vectors of tens of megabytes, it's kind of over. You can start playing games by accelerating capacity allocation when a vector rapidly starts growing extremely large. This doesn't solve the problem that vectors sometimes guarantee too much for what you need.
  - dilap 4y ago
    Ah thanks, I didn't read closely enough the first time.
samsquire 4y ago
For a simple and readable implementation of a Python btree see this: https://github.com/samsquire/btree https://github.com/samsquire/btree I tried to keep the implementation as simple as I could.

cobalt 4y ago

also what a deque (C++) does

pencilguin 4y ago
True... except in MSVC. std::deque in MSVC is cursed. Targeting MSVC, use boost::deque or something, instead. Boost containers are generally fairly good, although they are more or less unmaintained nowadays. (E.g., boost::unordered_map::reserve doesn't work.) Or, like many of us, ignore performance on MS targets because anybody who cares about performances is running something else.
- q-big 4y ago
  Why?
  - pencilguin 4y ago
    https://github.com/AcademySoftwareFoundation/openvdb/issues/1350 https://github.com/AcademySoftwareFoundation/openvdb/issues/... Longer answer is that the size of the "blocks" is limited to 512 bytes or one element, whichever is larger. So unless your elements are really tiny, it is strictly a pessimization.
- cyber_kinetist 4y ago
  Many of the STL containers in MSVC are incredibly cursed. Even std::vector is implemented in such a weird way, that you can't debug it easily with any debugger other than Visual Studio. And it's incredibly slow on Debug mode, up to the point that it's unusable... (Because of these reasons I just switched to using my own Vector<T> class recently) I think there's a very good reason why old gamedevs who were stuck with developing on Windows largely ignored the STL and made their own containers / utility functions: MSVC's STL was just awful.
  - brantonb 4y ago
    I always wondered why we weren’t allowed to use the STL in the Windows division in the 00’s. This probably explains it.