Mirror of forum.nim-lang.org

3554 :: Sorting

• twetzel59 (orginal) [2018-02-17T02:12:30+01:00] view original

  Hey everyone, this is quick post from my phone.

  I am reading Nim in Action and I have noticed that the algorithm module includes the sort proc which takes a procvar comparator.

  As a C programmer I am well aware of qsort performance issues due to indirection, cache misses etc from the virtual function call.

  Is the Nim sort in the same boat here, or can the compiler, say inline the comparison?

  Thx :)

---

• Stefan_Salewski (orginal) [2018-02-17T09:27:37+01:00] view original

  Yes, there is some performance decrease due to compare proc, but not too much, maybe about 25 % as I remember.

  See

  https://forum.nim-lang.org/t/2701#20961

---

• twetzel59 (orginal) [2018-02-17T15:08:16+01:00] view original

  Ok, I guess if I need an extremely fast sort I can create my own version based on the stdlib implementation that uses generics or templates.

  Thank you!

---

• Araq (orginal) [2018-02-18T17:27:21+01:00] view original

  Yeah we probably need to offer a sort that inlines the comparator. That said, I have seen the C compilers remove indirect calls if they can prove the jump destination (and for sort that is actually rather easy to determine).

---

• twetzel59 (orginal) [2018-02-18T20:34:47+01:00] view original

  Ok.

---

• Udiknedormin (orginal) [2018-02-19T09:47:49+01:00] view original

  @Stefan_Salewski Well, actually, 25% is a hell lot (anything over 5% is considerable, I think). I think it would be much easier if Nim enabled functor (not functor pointer!) types (i.e. any function or closure is a separate type). It would reduce the need for templates greatly, especially it ones.

---