Mirror of forum.nim-lang.org

2468 :: FastStack - dynamically resizable data structure optimized for fast iteration

• Vladar (orginal) [2016-08-14T23:46:57+02:00] view original

  https://github.com/Vladar4/FastStack

  FastStack is dynamically resizable data structure optimized for fast iteration over the large arrays of similar elements avoiding memory fragmentation (e.g., update and rendering cycles of a game scene).

  Judging by the benchmarks, it faster than seq on highly fragmented data, and almost as fast as seq on non-fragmented data.

---

• mbaulch (orginal) [2016-08-15T01:36:42+02:00] view original

  With the Boehm GC, seq is faster in both of your benchmarks. The default ref-counting GC definitely has limitations. Also, it's probably better to initialise FastStack to the same capacity as the seq. 1000 vs 0 isn't really fair.

---

• Vladar (orginal) [2016-08-15T12:10:53+02:00] view original

  With the Boehm GC, seq is faster

  With the Boehm GC all three are slower than with the default GC. Don't see a point of Boehm in such case.

  Also, it's probably better to initialise FastStack to the same capacity as the seq

  I'd better initialize the seq to the same capacity as FastStack, but I get a segfault on bench_ptr for some reason.

---

• mbaulch (orginal) [2016-08-15T13:23:39+02:00] view original

  My apologies. I only looked at seq and (mistakenly) assumed all were faster. On my (rather slow) laptop, the results of the ptr benchmark are

  
  refc:
  Sequence  2.70ms/iter
  List      2.99ms/iter
  FastStack 2.23ms/iter
  
  Boehm:
  Sequence  2.43ms/iter
  List      3.29ms/iter
  FastStack 2.54ms/iter
  Run

  FastStack with refc is indeed the winner, though seq with Boehm is not far behind.

  I get the same segfault. Will have to dig a bit more and see where the bug lies. Hope it's not in the GC!

  Edit: It seems Boehm is slower with the seq int benchmark, but faster with the seq ptr case. I'd argue the seq int case isn't a very realistic test.

---

• mora (orginal) [2016-08-15T15:00:05+02:00] view original

  Gc is giving back memory to the OS if there is 1 MB unused. When I increased that to 8 MB (I don't remember the exact location, maybe allocate.nim, or something like that), it helped a lot in these kind of benchmarks.

---