Re: Timing comparison between call/cc-safe and non-call/cc-safe procedures
Bradley Lucier 07 Aug 2022 23:57 UTC
I came up with code for call/cc-safe array-copy which keeps computed
array entries and multi-indices on the stack, instead of consing
computed array entries onto a list.
The basic loop for two dimensions looks like
((2)
(let ((lower-0 (%%interval-lower-bound interval 0))
(lower-1 (%%interval-lower-bound interval 1))
(upper-0 (%%interval-upper-bound interval 0))
(upper-1 (%%interval-upper-bound interval 1))
(i 0))
(let loop-0 ((i_0 lower-0) (i i))
(if (= i_0 upper-0)
((storage-class-maker storage-class)
(%%interval-volume interval)
(storage-class-default storage-class))
(let loop-1 ((i_1 lower-1) (i i))
(if (= i_1 upper-1)
(loop-0 (+ i_0 1) i)
(let ((item (A_ i_0 i_1)))
(if (checker item)
(let ((result (loop-1 (+ i_1 1) (+ i 1))))
(setter result i item)
result)
(error (wrap "Not all elements of the source can
be stored in destination: ")
item
A
storage-class)))))))))
where
(let* ((setter (storage-class-setter storage-class))
(checker (storage-class-checker storage-class))
(A_ (%%array-getter A))
(interval (%%array-domain A)))
In comparing timing results of the existing code and the new code, there
was no case where the new code was noticeably faster.
When the result is a specialized array with generic-storage-class, the
new code is slower than the existing code, which simply copies a
reversed list to a vector, but can specialize that one loop for
generic-storage-class and omit the call to checker (all values are valid
for the array) and inline the call to setter (which is simply vector-set!):
(if (eq? storage-class generic-storage-class)
(let loop ((i (fx- n 1))
(l reversed-elements))
(if (fx<= 0 i)
(begin
(vector-set! body i (car l))
(loop (fx- i 1)
(cdr l)))
(%%finish-specialized-array domain
storage-class
body
indexer
mutable?
safe?
#t)))
(let loop ((i (fx- n 1))
(l reversed-elements))
(if (fx<= 0 i)
(if (checker (car l))
(begin
(setter body i (car l))
(loop (fx- i 1)
(cdr l)))
(error (string-append message "Not all elements of
the source can be stored in destination: ") array storage-class mutable?
safe?))
(%%finish-specialized-array domain
storage-class
body
indexer
mutable?
safe?
#t))))
With the stack-based approach, it's too much to have two copies of the
code up top, one with the checker and setter for
non--generic-storage-classes, and one omitting the checker and using
vector-set! for generic storage classes, for each dimension. (Currently
I generate inline code like this for dimensions up to 8, then have some
ugly code for higher dimensions.)
So I'm going to stick with the simple code that just conses up a
reversed list and then copies the list elements to the relevant type of
vector.
I'm including the stack-based code here for reference.
Brad