Special case common `sort` usages

[primo-ppcg]

• Special case common sort usages (<, >) to use vm ops directly.
• Rewrite median-of-three to use 2.667 comparisons on average, rather than 5. It's not as clever, but it is faster.
• Avoid recursing if unnecessary.

The result is approximately 3x faster for these usages, and roughly unchanged for others.

(use spork/test)
(use spork/misc)

(def rng (math/rng 12345))
(def a (randomize-array (range 100) rng))

(timeit-loop [:timeout 1]
  "sorted "
  (sorted a))

(timeit-loop [:timeout 1]
  "sort   "
  (def b (array/slice a))
  (sort b))

(timeit-loop [:timeout 1]
  "reverse"
  (def b (array/slice a))
  (sort b >))

(timeit-loop [:timeout 1]
  "compare"
  (def b (array/slice a))
  (sort b compare<))

master:

sorted  1.000s, 99.43µs/body
sort    1.000s, 100.1µs/body
reverse 1.000s, 98.23µs/body
compare 1.000s, 131.7µs/body

branch:

sorted  1.000s, 28.41µs/body
sort    1.000s, 28.68µs/body
reverse 1.000s, 31.29µs/body
compare 1.000s, 126.9µs/body

[sogaiu]

Tangential question...

Regarding:

      (if (>= left right) (break)))
    (if (< lo right)
      (sort-help a lo right before?))
    (if (< left hi)
      (sort-help a left hi before?)))

I've been wondering why if over when sometimes (assuming no "else"-ish things). I know there are other cases of using if in boot.janet in a similar manner but I remain curious about motivations. Less to type?

In my own code I tend to use if for when there is an "else"...but clearly that's not how everyone sees things :)

[sogaiu]

Below are the numbers I got on a Linux box.

master (8df73643):

$ janet ~/scratch/pr-1255-sort.janet 
sorted  1.000s, 142.8µs/body
sort    1.000s, 138.2µs/body
reverse 1.000s, 149.5µs/body
compare 1.000s, 175.5µs/body

branch (cdd7083c):

$ JANET_PATH=$HOME/.local/lib/janet ~/src/janet.primo-ppcg/build/janet ~/scratch/pr-1255-sort.janet 
sorted  1.000s, 44.15µs/body
sort    1.000s, 43.94µs/body
reverse 1.000s, 47.01µs/body
compare 1.001s, 172.4µs/body

[pepe]

Tangential question...

@sogaiu I am using when only when there is more than one form in the body. My 2 cents tho :-).

[sogaiu]

I am using when only when there is more than one form in the body

Perhaps this is a bit like when one doesn't use braces in some spots in C when one can get away with it...increasing the chances of errors later if one forgets to make an appropriate modification when an additional line / form might need to be added? :)

[CosmicToast]

Right. I see (when ...) as an (if (do ...)) rather than a (if ...). Now that I check, this is somewhat unsurprising, as it is a macro that compiles to exactly that.

[primo-ppcg]

I've been wondering why if over when sometimes (assuming no "else"-ish things).

Because it creates an unnecessary scoping. A micro-optimization at best, but measurable.

"Don't prematurely over-optimize... but don't intentionally under-optimize either."

Perhaps this is a bit like when one doesn't use braces in some spots in C when one can get away with it...increasing the chances of errors later if one forgets to make an appropriate modification when an additional line / form might need to be added? :)

For my own projects, I always use braces, even for single statement bodies. When contributing to projects that are not my own, I try to match the given style as closely as possible. An if statement without braces should be immediately followed by a blank line, though.

[sogaiu]

I guess it would seem that the specific situation would matter.

If measurements suggest it would help, that makes sense. Otherwise, it doesn't seem like a clear winner to me. Particularly in languages without source step debugging where the expectation appears to be to modify one's source when investigating things, I think I'd prefer to use when / if the way I've been doing.

So in the case of this PR, may be it makes sense based on measurements.

[primo-ppcg]

So in the case of this PR, may be it makes sense based on measurements.

Actually, I doesn't seem to make a difference anymore. Perhaps the recent compiler optimizations have made the point moot. We're free to use when without feeling guilty :laughing:

Regarding the frequent use in boot.janet, I suspect it's the same reason as the frequent use of forv; until recently, it was faster than for.

[sogaiu]

We're free to use when without feeling guilty

Ah, thanks for sharing this info.

I guess what's tricky is that with folks like you optimizing things (thanks BTW!), it might be a never-ending game of figuring out what to write...oh, may be that's a feature? :)

[bakpakin]

Just for reference when vs if never impacted performance. Old code may have just used if instead of when because there used to be an else statement, or it is 2 characters shorter.

Anyway, LGTM.