M lib/scopes/compiler/uheap/api.sc +44 -4
@@ 240,7 240,7 @@ struct ANode plain
key : u64
pnodei : PNodeIndex
-inline lowerbound (self value keyf)
+#inline lowerbound (self value keyf)
""""Return the leftmost occurrence of `value` in sorted array `self`, or the
number of values smaller than `value`.
keyf := static-if (none? keyf) defaultkey
@@ 256,7 256,7 @@ inline lowerbound (self value keyf)
else
repeat L m
-inline upperbound (self value keyf)
+#inline upperbound (self value keyf)
""""Return the index of the first value greater than `value` (or the size
of the array itself).
keyf := static-if (none? keyf) defaultkey
@@ 303,6 303,44 @@ struct UHeap
stackaddr : intptr
globaladdrs : Array (tuple intptr usize)
+ fn startoffset (self offset count start)
+ # return offset x0
+ x0 := fold (x0 = 0:usize) for i in (range count)
+ x := self.indices @ (offset + i)
+ n := self.nodes @ x
+ x1 := x0 + n.size
+ #print "x0" x0 "x1" x1 (x1 > start)
+ if (x1 > start)
+ return i x0
+ repeat x1
+ return count x0
+
+ fn startoffset_fast (self offset count start)
+ #slow_offset slow_x0 := startoffset_slow self offset count start
+ L := offset
+ R := offset + count
+ #print L ".." R "|" start
+ x0 := (offset == 0) 0:usize (self.indexsize @ (offset - 1))
+ #for i in (range count)
+ x1 := ((offset + i) == 0) 0:usize (self.indexsize @ (offset + i - 1))
+ print i "->" (x1 - x0)
+ #print "total" ((self.indexsize @ (R - 1)) - x0)
+ loop (L R)
+ if (L >= R)
+ x1 := (L == 0) 0:usize (self.indexsize @ (L - 1))
+ #print "done" (L - offset) (x1 - x0)
+ #print "should be" slow_offset slow_x0
+ #assert ((L - offset) == slow_offset)
+ #assert ((x1 - x0) == slow_x0)
+ break (L - offset) (x1 - x0)
+ m := (L + R) // 2
+ x1 := self.indexsize @ m
+ #print m (x1 - x0)
+ if ((x1 - x0) <= start)
+ repeat (m + 1) R
+ else
+ repeat L m
+
inline init-hnode (self)
idx := (countof self.hnodes) as i32
'append self.hnodes (HNode)
@@ 715,7 753,8 @@ inline gen_uheap_data_iterate_slices (te
case join (offset count)
if (enterf node start end)
db := (uheap_instance)
- fold (x0 = 0:usize) for i in (range count)
+ starti x0 := 'startoffset db (copy offset) (copy count) start
+ fold (x0) for i in (range starti count)
if (x0 >= end)
break x0
x := db.indices @ (offset + i)
@@ 1059,7 1098,8 @@ fn uheap_flatten_prim (dest n start end)
local last : PNodeDataIndex
local t0 = 0:usize
local t1 = 0:usize
- fold (x0 = 0:usize) for i in (range count)
+ starti x0 := 'startoffset db (copy offset) (copy count) start
+ fold (x0) for i in (range starti count)
x := db.indices @ (offset + i)
m := db.nodes @ x
x1 := x0 + m.size
M lib/scopes/core.sc +14 -9
@@ 9999,7 9999,7 @@ inline dot (u v)
inline length (v)
sqrt (dot v v)
-inline build_matching_real_vector (value c)
+inline build_matching_vector (value c)
let T = (typeof value)
let ST = (storageof T)
static-if (ST < vector)
@@ 10013,7 10013,7 @@ inline build_matching_real_vector (value
inline normalize (v)
fdiv v
- build_matching_real_vector v (length v)
+ build_matching_vector v (length v)
inline distance (a b)
length (a - b)
@@ 10033,7 10033,7 @@ inline fmix (a b c)
A B C := typeof a, typeof b, typeof c
static-assert ((A == B) and (B == C))
a b c := storagecast a, storagecast b, storagecast c
- let one = (build_matching_real_vector a 1)
+ let one = (build_matching_vector a 1)
let invx = (fsub one c)
bitcast (fadd (fmul a invx) (fmul b c)) A
@@ 10041,13 10041,18 @@ inline step (a b)
A B := typeof a, typeof b
static-assert (A == B)
a b := storagecast a, storagecast b
- let one = (build_matching_real_vector a 1)
- let zero = (build_matching_real_vector b 0)
+ let one = (build_matching_vector a 1)
+ let zero = (build_matching_vector b 0)
bitcast (? (fcmp>o a b) zero one) A
+inline ssign (x)
+ let zero = (build_matching_vector x 0)
+ let T = (typeof x)
+ sub (zext (< zero x) T) (zext (< x zero) T)
+
inline fsign (x)
# (0 < x) - (x < 0)
- let zero = (build_matching_real_vector x 0)
+ let zero = (build_matching_vector x 0)
let T = (typeof x)
fsub (uitofp (fcmp<o zero x) T) (uitofp (fcmp<o x zero) T)
@@ 10059,7 10064,7 @@ inline radians (x)
let ST = (storageof T)
static-if (ST < vector)
fmul x
- build_matching_real_vector x deg2rad
+ build_matching_vector x deg2rad
else
let x = (x as real)
x * (deg2rad as (typeof x))
@@ 10070,7 10075,7 @@ inline degrees (x)
let ST = (storageof T)
static-if (ST < vector)
fmul x
- build_matching_real_vector x rad2deg
+ build_matching_vector x rad2deg
else
let x = (x as real)
x * (rad2deg as (typeof x))
@@ 11120,7 11125,7 @@ spice autocopy (value...)
unlet _memo dot-char dot-sym ellipsis-symbol _Value constructor destructor
\ gen-tupleof nested-struct-field-accessor nested-union-field-accessor
\ tuple-comparison gen-arrayof MethodsAccessor-typeattr floorf modules
- \ string-array-ref-type? build_matching_real_vector
+ \ string-array-ref-type? build_matching_vector
# about to be removed
#unlet include sc_import_c
M lib/scopes/hash.sc +9 -0
@@ 334,6 334,12 @@ fn sc_hash2x64 (a b)
# function to invert large odd number
inline... mod_inverse_2
+case (a : u32)
+ x := (a * a) + a - 1:u32 # 4
+ x := x * (2:u32 - a * x) # 8
+ x := x * (2:u32 - a * x) # 16
+ x := x * (2:u32 - a * x) # 32
+ x
case (a : u64)
x := (a * a) + a - 1:u64 # 4
x := x * (2:u64 - a * x) # 8
@@ 350,6 356,9 @@ case (a : u128)
x := x * (2:u64 - a * x) # 128
x
+#print
+ mod_inverse_2 2654435789:u32
+
inline unpack-u128 (x)
(x >> 64) as u64, x as u64
inline pack-u128 (h1 h2)
M testing/test_mutarray.sc +8 -4
@@ 442,6 442,10 @@ do
t @ i = k
;
+# mip binary search:
+#while (k <= n)
+ k = 2 * k + (b[k] < x)
+
fn tree2mipl (x)
b := x & -x
level := findlsb b
@@ 459,11 463,11 @@ fn mip2tree (x maxlevel)
q := 1 << (findmsb x)
((1 << maxlevel) // q) * ((x - q) * 2 + 1)
-MAXLEVEL := 3
-for x in (range 1 16)
- print x "=>" (mip2tree x MAXLEVEL)
+MAXLEVEL := 6
+for x in (range 100)
+ print x "=>" ((mip2tree x MAXLEVEL) - 1)
-for x in (range 1 16)
+#for x in (range 100)
level offset := tree2mipl x
x1 := mipl2tree level offset
x2 := tree2mip x MAXLEVEL