opendylan
opendylan copied to clipboard
limited vector 2X slower than standard vector
https://play.opendylan.org/shared/a2f00e2c85f0806b shows some quicksort code with two definitions of <vec>, one commented out. If you run it both ways you'll see that when <vec> is the limited type the code is twice as slow, whereas I would expect it to be faster.
Looking at the DFM for both, I can see what looks like it might be additional bounds checks? It looks similar to the issue documented here: https://opendylan.org/documentation/release-notes/2012.1.html#limited-collections
Standard vector DFM...
METHOD quicksort! (a :: <vector>, lo, hi) => (#rest results)
{{ lo }} := make-cell({{ lo }}) @???
| {{ lo }} :: <object>
\ {{ lo }} :: <bottom>
t50 := cell-value({{ lo }}) @perf.dylan:75
\ t50 :: <object>
{{ i }} := make-cell(t50) @perf.dylan:75
\ {{ i }} :: <bottom>
{{ j }} := make-cell({{ hi }}) @perf.dylan:76
| {{ hi }} :: <object>
\ {{ j }} :: <bottom>
LOOP ()
t52 := cell-value({{ i }}) @perf.dylan:77
\ t52 :: <object>
t42 := [CONGRUENT-CALLg ^{<&generic> <}(t52, {{ hi }})] @perf.dylan:77
| ^{<&generic> <} :: singleton(<)
\ t42 :: <boolean>
IF (t42)
t49 := cell-value({{ lo }}) @perf.dylan:78
\ t49 :: <object>
t3 := [CONGRUENT-CALLg ^{<&generic> +}(t49, {{ hi }})] @perf.dylan:78
| ^{<&generic> +} :: singleton(+)
\ t3 :: <object>
t4 := [CALLg ^{<&generic> floor/}(t3, ^2)] @perf.dylan:78
| ^{<&generic> floor/} :: singleton(floor/)
| ^2 :: singleton(2)
\ t4 :: <integer>
{{ pivot }} := [CONGRUENT-CALLg ^{<&generic> element}({{ a }}, t4, ^#[])] @perf.dylan:78
| ^{<&generic> element} :: singleton(element)
| {{ a }} :: <vector>
| ^#[] :: singleton(#[])
\ {{ pivot }} :: <object>
LOOP ()
t54 := cell-value({{ i }}) @perf.dylan:79
\ t54 :: <object>
t64 := cell-value({{ j }}) @perf.dylan:79
\ t64 :: <object>
t71 := [CONGRUENT-CALLg ^{<&generic> <}(t64, t54)] @perf.dylan:79
| ^{<&generic> <} :: singleton(<)
\ t71 :: <boolean>
IF (t71)
ELSE
LOOP ()
...
Limited vector DFM...
METHOD quicksort! (a :: limited(<vector>, #"of", <double-float>), lo, hi) => (#rest results)
{{ lo }} := make-cell({{ lo }}) @???
| {{ lo }} :: <object>
\ {{ lo }} :: <bottom>
t50 := cell-value({{ lo }}) @perf.dylan:75
\ t50 :: <object>
{{ i }} := make-cell(t50) @perf.dylan:75
\ {{ i }} :: <bottom>
{{ j }} := make-cell({{ hi }}) @perf.dylan:76
| {{ hi }} :: <object>
\ {{ j }} :: <bottom>
LOOP ()
t52 := cell-value({{ i }}) @perf.dylan:77
\ t52 :: <object>
t42 := [CONGRUENT-CALLg ^{<&generic> <}(t52, {{ hi }})] @perf.dylan:77
| ^{<&generic> <} :: singleton(<)
\ t42 :: <boolean>
IF (t42)
t49 := cell-value({{ lo }}) @perf.dylan:78
\ t49 :: <object>
t3 := [CONGRUENT-CALLg ^{<&generic> +}(t49, {{ hi }})] @perf.dylan:78
| ^{<&generic> +} :: singleton(+)
\ t3 :: <object>
t4 := [CALLg ^{<&generic> floor/}(t3, ^2)] @perf.dylan:78
| ^{<&generic> floor/} :: singleton(floor/)
| ^2 :: singleton(2)
\ t4 :: <integer>
t73 := SLOT-VALUE-INITD({{ a }}, size) @perf.dylan:78
| {{ a }} :: <simple-double-float-vector>
\ t73 :: <integer>
t74 := [PRIMOP cast-integer-as-raw(t4)] @perf.dylan:78
\ t74 :: <raw-machine-word>
t75 := [PRIMOP cast-integer-as-raw(t73)] @perf.dylan:78
\ t75 :: <raw-machine-word>
t76 := [PRIMOP machine-word-unsigned-less-than?(t74, t75)] @perf.dylan:78
\ t76 :: <boolean>
IF (t76)
t77 := REPEATED-SLOT-VALUE({{ a }}, double-float-vector-element, t74) @perf.dylan:78
\ t77 :: <raw-double-float>
t78 := [PRIMOP raw-as-double-float(t77)] @perf.dylan:78
\ t78 :: <double-float>
ELSE
*t81(1) := [CONGRUENT-CALLi ^{<&method> element-range-error (<collection>, <object>)}({{ a }}, t4)] @perf.dylan:78
| ^{<&method> element-range-error (<collection>, <object>)} :: singleton({<&method> element-range-error (collection :: <collection>, key) => (will-never-return :: <bottom>)})
\ *t81(1) :: values(#rest <bottom>)
t87 := *t81(1) [0] @perf.dylan:78
\ t87 :: <bottom>
END IF
t90 := [IF-MERGE t78 t87] @perf.dylan:78
\ t90 :: <double-float>
LOOP ()
t54 := cell-value({{ i }}) @perf.dylan:79
\ t54 :: <object>
t64 := cell-value({{ j }}) @perf.dylan:79
\ t64 :: <object>
t85 := [CONGRUENT-CALLg ^{<&generic> <}(t64, t54)] @perf.dylan:79
| ^{<&generic> <} :: singleton(<)
\ t85 :: <boolean>
IF (t85)
ELSE
LOOP ()
...