Mirror of forum.nim-lang.org

5643 :: Most efficient way to implement a stack using Nim?

• drkameleon (orginal) [2019-12-05T10:36:21+01:00] view original

  OK, so I've been playing and benchmarking ideas of how to implement an (uint64) stack in Nim. (seq-based, array-based, and timing push'es and pop's)

  How would you approach this? (my main concern is speed)

---

• mratsim (orginal) [2019-12-05T11:39:46+01:00] view original

  Assuming that:

  • it's used in a hot-loop and so that the data of both array and seq are hot in the CPU cache
  • both are properly dimensioned and don't need realloc
  • your indexes and stack length are using int32 or int64 to avoid slower int8/int16 operations that also needs to zero the upper part of your registers

  There should be no difference.

  The only optimization I see that could improve perf is not using a stack at all (but just to avoid allocations) if your algorithm can accomodate that (i.e. stackless depth first search for example) but we would need more context.

  Stacks are very very fast.

---

• zevv (orginal) [2019-12-05T20:23:38+01:00] view original

  I use seqs as stacks extensively in one of my projects, and I found these are generally ok unless you need to unwind your stack frames more then one item at a time: I believe setLen() can invoke the GC and cause performance degradation. Instead, I use a seq for storage but keep my own top value and provide some access functions which merely update the top value and read/write the seq's contents.

---

• sschwarzer (orginal) [2019-12-05T22:52:16+01:00] view original

  If you know roughly how large the stack seq can get, you may want to try

  https://nim-lang.org/docs/system.html#newSeqOfCap%2CNatural

  to avoid or reduce reallocations.

  In a small benchmark I wrote some time ago, using newSeqOfCap to set the initial capacity made a noticable difference compared to using newSeq.

---

• treeform (orginal) [2019-12-05T23:13:23+01:00] view original

  I agree on newSeqOfCap, reallocations can be expensive.

---