opendylan icon indicating copy to clipboard operation
opendylan copied to clipboard

limited vector 2X slower than standard vector

Open cgay opened this issue 4 years ago • 1 comments

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

cgay avatar Jan 02 '21 06:01 cgay

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 ()
...

cgay avatar Jan 02 '21 06:01 cgay