Skip to content

Remove initialized memory for offset elements

Compare
Choose a tag to compare
@orxfun orxfun released this 29 Aug 20:50
· 20 commits to main since this release
d2c91ea
  • Tree initialization is revised to establish miri safety:
    • miri tests on the prior versions failed due to the uninitialized data in the first offset elements of the vector backing the tree. Note that the implementation guarantees that these elements are never accessed.
    • One potential solution to avoid uninitialized elements was to require Default or PseudoDefault for tree nodes. Most probably, this could have worked in most practical use cases. However, one exception is references. It might be considered a practical case where nodes are references, which would not implement neither Default or PseudoDefault.
    • Since we require Clone, another solution would be to fill the offset elements with the first ever pushed node to the queue. In other words, tree initialization is delayed until the first element is pushed. The concern on this was its potential impact of the additional "is backing vector empty" check on push methods. However, benchmarks show that this check does no measurable impact on the performance.
    • Since the latter solution does not add a trait requirement on keys or values, and since it does not degrade performance, it is implemented in this PR.
    • With the updated & delayed tree initialization without assume_init, all miri tests pass.
  • Minor fix in no-std configurations.
  • Benchmark runs are repeated.
  • Documentation is revised.