diff options
| author | ftphikari <ftphikari@gmail.com> | 2023-07-25 15:32:18 +0300 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-07-25 15:32:18 +0300 |
| commit | 699aec331d44da58bceddfb788bf349995473ad9 (patch) | |
| tree | 3f5ce42c72c18fff1fc79f0229797be72f0e7638 /core/runtime | |
| parent | d2375a79f29d8377c813484bce3127ae9c205974 (diff) | |
| parent | 5ac7fe453f5fbf0995c24f0c1c12ed439ae3aee9 (diff) | |
Merge branch 'odin-lang:master' into master
Diffstat (limited to 'core/runtime')
| -rw-r--r-- | core/runtime/core.odin | 2 | ||||
| -rw-r--r-- | core/runtime/core_builtin.odin | 12 | ||||
| -rw-r--r-- | core/runtime/default_allocators_js.odin | 4 | ||||
| -rw-r--r-- | core/runtime/default_allocators_nil.odin | 50 | ||||
| -rw-r--r-- | core/runtime/default_allocators_wasi.odin | 4 | ||||
| -rw-r--r-- | core/runtime/dynamic_map_internal.odin | 216 | ||||
| -rw-r--r-- | core/runtime/error_checks.odin | 22 | ||||
| -rw-r--r-- | core/runtime/internal.odin | 33 | ||||
| -rw-r--r-- | core/runtime/print.odin | 4 |
9 files changed, 218 insertions, 129 deletions
diff --git a/core/runtime/core.odin b/core/runtime/core.odin index 058ca6161..83504c9ee 100644 --- a/core/runtime/core.odin +++ b/core/runtime/core.odin @@ -566,7 +566,7 @@ __type_info_of :: proc "contextless" (id: typeid) -> ^Type_Info #no_bounds_check return &type_table[n] } -when !ODIN_DISALLOW_RTTI { +when !ODIN_NO_RTTI { typeid_base :: proc "contextless" (id: typeid) -> typeid { ti := type_info_of(id) ti = type_info_base(ti) diff --git a/core/runtime/core_builtin.odin b/core/runtime/core_builtin.odin index c5cb8cc07..9f2899bcc 100644 --- a/core/runtime/core_builtin.odin +++ b/core/runtime/core_builtin.odin @@ -112,7 +112,7 @@ remove_range :: proc(array: ^$D/[dynamic]$T, lo, hi: int, loc := #caller_locatio // Note: If the dynamic array as no elements (`len(array) == 0`), this procedure will panic. @builtin pop :: proc(array: ^$T/[dynamic]$E, loc := #caller_location) -> (res: E) #no_bounds_check { - assert(len(array) > 0, "", loc) + assert(len(array) > 0, loc=loc) res = array[len(array)-1] (^Raw_Dynamic_Array)(array).len -= 1 return res @@ -136,7 +136,7 @@ pop_safe :: proc(array: ^$T/[dynamic]$E) -> (res: E, ok: bool) #no_bounds_check // Note: If the dynamic array as no elements (`len(array) == 0`), this procedure will panic. @builtin pop_front :: proc(array: ^$T/[dynamic]$E, loc := #caller_location) -> (res: E) #no_bounds_check { - assert(len(array) > 0, "", loc) + assert(len(array) > 0, loc=loc) res = array[0] if len(array) > 1 { copy(array[0:], array[1:]) @@ -424,7 +424,7 @@ append_elem :: proc(array: ^$T/[dynamic]$E, arg: E, loc := #caller_location) -> a := (^Raw_Dynamic_Array)(array) when size_of(E) != 0 { data := ([^]E)(a.data) - assert(condition=data != nil, loc=loc) + assert(data != nil, loc=loc) data[a.len] = arg } a.len += 1 @@ -459,7 +459,7 @@ append_elems :: proc(array: ^$T/[dynamic]$E, args: ..E, loc := #caller_location) a := (^Raw_Dynamic_Array)(array) when size_of(E) != 0 { data := ([^]E)(a.data) - assert(condition=data != nil, loc=loc) + assert(data != nil, loc=loc) intrinsics.mem_copy(&data[a.len], raw_data(args), size_of(E) * arg_len) } a.len += arg_len @@ -472,7 +472,7 @@ append_elems :: proc(array: ^$T/[dynamic]$E, args: ..E, loc := #caller_location) @builtin append_elem_string :: proc(array: ^$T/[dynamic]$E/u8, arg: $A/string, loc := #caller_location) -> (n: int, err: Allocator_Error) #optional_allocator_error { args := transmute([]E)arg - return append_elems(array=array, args=args, loc=loc) + return append_elems(array, ..args, loc=loc) } @@ -481,7 +481,7 @@ append_elem_string :: proc(array: ^$T/[dynamic]$E/u8, arg: $A/string, loc := #ca append_string :: proc(array: ^$T/[dynamic]$E/u8, args: ..string, loc := #caller_location) -> (n: int, err: Allocator_Error) #optional_allocator_error { n_arg: int for arg in args { - n_arg, err = append(array = array, args = transmute([]E)(arg), loc = loc) + n_arg, err = append(array, ..transmute([]E)(arg), loc=loc) n += n_arg if err != nil { return diff --git a/core/runtime/default_allocators_js.odin b/core/runtime/default_allocators_js.odin index cc70b963a..715073f08 100644 --- a/core/runtime/default_allocators_js.odin +++ b/core/runtime/default_allocators_js.odin @@ -1,5 +1,5 @@ //+build js package runtime -default_allocator_proc :: nil_allocator_proc -default_allocator :: nil_allocator +default_allocator_proc :: panic_allocator_proc +default_allocator :: panic_allocator diff --git a/core/runtime/default_allocators_nil.odin b/core/runtime/default_allocators_nil.odin index f86990581..a340050eb 100644 --- a/core/runtime/default_allocators_nil.odin +++ b/core/runtime/default_allocators_nil.odin @@ -35,4 +35,52 @@ nil_allocator :: proc() -> Allocator { when ODIN_OS == .Freestanding { default_allocator_proc :: nil_allocator_proc default_allocator :: nil_allocator -}
\ No newline at end of file +} + + + +panic_allocator_proc :: proc(allocator_data: rawptr, mode: Allocator_Mode, + size, alignment: int, + old_memory: rawptr, old_size: int, loc := #caller_location) -> ([]byte, Allocator_Error) { + switch mode { + case .Alloc: + if size > 0 { + panic("panic allocator, .Alloc called", loc=loc) + } + case .Alloc_Non_Zeroed: + if size > 0 { + panic("panic allocator, .Alloc_Non_Zeroed called", loc=loc) + } + case .Resize: + if size > 0 { + panic("panic allocator, .Resize called", loc=loc) + } + case .Free: + if old_memory != nil { + panic("panic allocator, .Free called", loc=loc) + } + case .Free_All: + panic("panic allocator, .Free_All called", loc=loc) + + case .Query_Features: + set := (^Allocator_Mode_Set)(old_memory) + if set != nil { + set^ = {.Query_Features} + } + return nil, nil + + case .Query_Info: + panic("panic allocator, .Query_Info called", loc=loc) + } + + return nil, nil +} + +panic_allocator :: proc() -> Allocator { + return Allocator{ + procedure = nil_allocator_proc, + data = nil, + } +} + + diff --git a/core/runtime/default_allocators_wasi.odin b/core/runtime/default_allocators_wasi.odin index 2e475e055..a7e6842a6 100644 --- a/core/runtime/default_allocators_wasi.odin +++ b/core/runtime/default_allocators_wasi.odin @@ -1,5 +1,5 @@ //+build wasi package runtime -default_allocator_proc :: nil_allocator_proc -default_allocator :: nil_allocator +default_allocator_proc :: panic_allocator_proc +default_allocator :: panic_allocator diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 05c03028f..d34c29d4b 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -414,68 +414,21 @@ map_insert_hash_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^ tk := map_cell_index_dynamic(sk, info.ks, 1) tv := map_cell_index_dynamic(sv, info.vs, 1) - for { - hp := &hs[pos] - element_hash := hp^ + swap_loop: for { + element_hash := hs[pos] if map_hash_is_empty(element_hash) { - kp := map_cell_index_dynamic(ks, info.ks, pos) - vp := map_cell_index_dynamic(vs, info.vs, pos) - intrinsics.mem_copy_non_overlapping(rawptr(kp), rawptr(k), size_of_k) - intrinsics.mem_copy_non_overlapping(rawptr(vp), rawptr(v), size_of_v) - hp^ = h + k_dst := map_cell_index_dynamic(ks, info.ks, pos) + v_dst := map_cell_index_dynamic(vs, info.vs, pos) + intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) + intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) + hs[pos] = h - return result if result != 0 else vp + return result if result != 0 else v_dst } if map_hash_is_deleted(element_hash) { - next_pos := (pos + 1) & mask - - // backward shift - for !map_hash_is_empty(hs[next_pos]) { - probe_distance := map_probe_distance(m^, hs[next_pos], next_pos) - if probe_distance == 0 { - break - } - probe_distance -= 1 - - kp := map_cell_index_dynamic(ks, info.ks, pos) - vp := map_cell_index_dynamic(vs, info.vs, pos) - kn := map_cell_index_dynamic(ks, info.ks, next_pos) - vn := map_cell_index_dynamic(vs, info.vs, next_pos) - - if distance > probe_distance { - if result == 0 { - result = vp - } - // move stored into pos; store next - intrinsics.mem_copy_non_overlapping(rawptr(kp), rawptr(k), size_of_k) - intrinsics.mem_copy_non_overlapping(rawptr(vp), rawptr(v), size_of_v) - hs[pos] = h - - intrinsics.mem_copy_non_overlapping(rawptr(k), rawptr(kn), size_of_k) - intrinsics.mem_copy_non_overlapping(rawptr(v), rawptr(vn), size_of_v) - h = hs[next_pos] - } else { - // move next back 1 - intrinsics.mem_copy_non_overlapping(rawptr(kp), rawptr(kn), size_of_k) - intrinsics.mem_copy_non_overlapping(rawptr(vp), rawptr(vn), size_of_v) - hs[pos] = hs[next_pos] - distance = probe_distance - } - hs[next_pos] = 0 - pos = (pos + 1) & mask - next_pos = (next_pos + 1) & mask - distance += 1 - } - - kp := map_cell_index_dynamic(ks, info.ks, pos) - vp := map_cell_index_dynamic(vs, info.vs, pos) - intrinsics.mem_copy_non_overlapping(rawptr(kp), rawptr(k), size_of_k) - intrinsics.mem_copy_non_overlapping(rawptr(vp), rawptr(v), size_of_v) - hs[pos] = h - - return result if result != 0 else vp + break swap_loop } if probe_distance := map_probe_distance(m^, element_hash, pos); distance > probe_distance { @@ -495,8 +448,8 @@ map_insert_hash_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^ intrinsics.mem_copy_non_overlapping(rawptr(vp), rawptr(tv), size_of_v) th := h - h = hp^ - hp^ = th + h = hs[pos] + hs[pos] = th distance = probe_distance } @@ -504,6 +457,103 @@ map_insert_hash_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^ pos = (pos + 1) & mask distance += 1 } + + // backward shift loop + hs[pos] = 0 + look_ahead: uintptr = 1 + for { + la_pos := (pos + look_ahead) & mask + element_hash := hs[la_pos] + + if map_hash_is_deleted(element_hash) { + look_ahead += 1 + hs[la_pos] = 0 + continue + } + + k_dst := map_cell_index_dynamic(ks, info.ks, pos) + v_dst := map_cell_index_dynamic(vs, info.vs, pos) + + if map_hash_is_empty(element_hash) { + intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) + intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) + hs[pos] = h + + return result if result != 0 else v_dst + } + + k_src := map_cell_index_dynamic(ks, info.ks, la_pos) + v_src := map_cell_index_dynamic(vs, info.vs, la_pos) + probe_distance := map_probe_distance(m^, element_hash, la_pos) + + if probe_distance < look_ahead { + // probed can be made ideal while placing saved (ending condition) + if result == 0 { + result = v_dst + } + intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) + intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) + hs[pos] = h + + // This will be an ideal move + pos = (la_pos - probe_distance) & mask + look_ahead -= probe_distance + + // shift until we hit ideal/empty + for probe_distance != 0 { + k_dst = map_cell_index_dynamic(ks, info.ks, pos) + v_dst = map_cell_index_dynamic(vs, info.vs, pos) + + intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k_src), size_of_k) + intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v_src), size_of_v) + hs[pos] = element_hash + hs[la_pos] = 0 + + pos = (pos + 1) & mask + la_pos = (la_pos + 1) & mask + look_ahead = (la_pos - pos) & mask + element_hash = hs[la_pos] + if map_hash_is_empty(element_hash) { + return + } + + probe_distance = map_probe_distance(m^, element_hash, la_pos) + if probe_distance == 0 { + return + } + // can be ideal? + if probe_distance < look_ahead { + pos = (la_pos - probe_distance) & mask + } + k_src = map_cell_index_dynamic(ks, info.ks, la_pos) + v_src = map_cell_index_dynamic(vs, info.vs, la_pos) + } + return + } else if distance < probe_distance - look_ahead { + // shift back probed + intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k_src), size_of_k) + intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v_src), size_of_v) + hs[pos] = element_hash + hs[la_pos] = 0 + } else { + // place saved, save probed + if result == 0 { + result = v_dst + } + intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) + intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) + hs[pos] = h + + intrinsics.mem_copy_non_overlapping(rawptr(k), rawptr(k_src), size_of_k) + intrinsics.mem_copy_non_overlapping(rawptr(v), rawptr(v_src), size_of_v) + h = hs[la_pos] + hs[la_pos] = 0 + distance = probe_distance - look_ahead + } + + pos = (pos + 1) & mask + distance += 1 + } } @(require_results) @@ -696,49 +746,19 @@ map_erase_dynamic :: #force_inline proc "contextless" (#no_alias m: ^Raw_Map, #n m.len -= 1 ok = true - { // coalesce tombstones - // HACK NOTE(bill): This is an ugly bodge but it is coalescing the tombstone slots - mask := (uintptr(1)<<map_log2_cap(m^)) - 1 - curr_index := uintptr(index) - - // TODO(bill): determine a good value for this empirically - // if we do not implement backward shift deletion - PROBE_COUNT :: 8 - for _ in 0..<PROBE_COUNT { - next_index := (curr_index + 1) & mask - if next_index == index { - // looped around - break - } - - // if the next element is empty or has zero probe distance, then any lookup - // will always fail on the next, so we can clear both of them - hash := hs[next_index] - if map_hash_is_empty(hash) || map_probe_distance(m^, hash, next_index) == 0 { - hs[curr_index] = 0 - return - } - - // now the next element will have a probe count of at least one, - // so it can use the delete slot instead - hs[curr_index] = hs[next_index] - - mem_copy_non_overlapping( - rawptr(map_cell_index_dynamic(ks, info.ks, curr_index)), - rawptr(map_cell_index_dynamic(ks, info.ks, next_index)), - int(info.ks.size_of_type), - ) - mem_copy_non_overlapping( - rawptr(map_cell_index_dynamic(vs, info.vs, curr_index)), - rawptr(map_cell_index_dynamic(vs, info.vs, next_index)), - int(info.vs.size_of_type), - ) - - curr_index = next_index - } + mask := (uintptr(1)<<map_log2_cap(m^)) - 1 + curr_index := uintptr(index) + next_index := (curr_index + 1) & mask + // if the next element is empty or has zero probe distance, then any lookup + // will always fail on the next, so we can clear both of them + hash := hs[next_index] + if map_hash_is_empty(hash) || map_probe_distance(m^, hash, next_index) == 0 { + hs[curr_index] = 0 + } else { hs[curr_index] |= TOMBSTONE_MASK } + return } diff --git a/core/runtime/error_checks.odin b/core/runtime/error_checks.odin index 8539c724d..c189642af 100644 --- a/core/runtime/error_checks.odin +++ b/core/runtime/error_checks.odin @@ -22,7 +22,7 @@ bounds_check_error :: proc "contextless" (file: string, line, column: i32, index return } @(cold) - handle_error :: proc "contextless" (file: string, line, column: i32, index, count: int) { + handle_error :: proc "contextless" (file: string, line, column: i32, index, count: int) -> ! { print_caller_location(Source_Code_Location{file, line, column, ""}) print_string(" Index ") print_i64(i64(index)) @@ -83,7 +83,7 @@ dynamic_array_expr_error :: proc "contextless" (file: string, line, column: i32, return } @(cold) - handle_error :: proc "contextless" (file: string, line, column: i32, low, high, max: int) { + handle_error :: proc "contextless" (file: string, line, column: i32, low, high, max: int) -> ! { print_caller_location(Source_Code_Location{file, line, column, ""}) print_string(" Invalid dynamic array indices ") print_i64(i64(low)) @@ -104,7 +104,7 @@ matrix_bounds_check_error :: proc "contextless" (file: string, line, column: i32 return } @(cold) - handle_error :: proc "contextless" (file: string, line, column: i32, row_index, column_index, row_count, column_count: int) { + handle_error :: proc "contextless" (file: string, line, column: i32, row_index, column_index, row_count, column_count: int) -> ! { print_caller_location(Source_Code_Location{file, line, column, ""}) print_string(" Matrix indices [") print_i64(i64(row_index)) @@ -122,13 +122,13 @@ matrix_bounds_check_error :: proc "contextless" (file: string, line, column: i32 } -when ODIN_DISALLOW_RTTI { +when ODIN_NO_RTTI { type_assertion_check :: proc "contextless" (ok: bool, file: string, line, column: i32) { if ok { return } @(cold) - handle_error :: proc "contextless" (file: string, line, column: i32) { + handle_error :: proc "contextless" (file: string, line, column: i32) -> ! { print_caller_location(Source_Code_Location{file, line, column, ""}) print_string(" Invalid type assertion\n") type_assertion_trap() @@ -141,7 +141,7 @@ when ODIN_DISALLOW_RTTI { return } @(cold) - handle_error :: proc "contextless" (file: string, line, column: i32) { + handle_error :: proc "contextless" (file: string, line, column: i32) -> ! { print_caller_location(Source_Code_Location{file, line, column, ""}) print_string(" Invalid type assertion\n") type_assertion_trap() @@ -154,7 +154,7 @@ when ODIN_DISALLOW_RTTI { return } @(cold) - handle_error :: proc "contextless" (file: string, line, column: i32, from, to: typeid) { + handle_error :: proc "contextless" (file: string, line, column: i32, from, to: typeid) -> ! { print_caller_location(Source_Code_Location{file, line, column, ""}) print_string(" Invalid type assertion from ") print_typeid(from) @@ -199,7 +199,7 @@ when ODIN_DISALLOW_RTTI { } @(cold) - handle_error :: proc "contextless" (file: string, line, column: i32, from, to: typeid, from_data: rawptr) { + handle_error :: proc "contextless" (file: string, line, column: i32, from, to: typeid, from_data: rawptr) -> ! { actual := variant_type(from, from_data) @@ -225,7 +225,7 @@ make_slice_error_loc :: #force_inline proc "contextless" (loc := #caller_locatio return } @(cold) - handle_error :: proc "contextless" (loc: Source_Code_Location, len: int) { + handle_error :: proc "contextless" (loc: Source_Code_Location, len: int) -> ! { print_caller_location(loc) print_string(" Invalid slice length for make: ") print_i64(i64(len)) @@ -240,7 +240,7 @@ make_dynamic_array_error_loc :: #force_inline proc "contextless" (using loc := # return } @(cold) - handle_error :: proc "contextless" (loc: Source_Code_Location, len, cap: int) { + handle_error :: proc "contextless" (loc: Source_Code_Location, len, cap: int) -> ! { print_caller_location(loc) print_string(" Invalid dynamic array parameters for make: ") print_i64(i64(len)) @@ -257,7 +257,7 @@ make_map_expr_error_loc :: #force_inline proc "contextless" (loc := #caller_loca return } @(cold) - handle_error :: proc "contextless" (loc: Source_Code_Location, cap: int) { + handle_error :: proc "contextless" (loc: Source_Code_Location, cap: int) -> ! { print_caller_location(loc) print_string(" Invalid map capacity for make: ") print_i64(i64(cap)) diff --git a/core/runtime/internal.odin b/core/runtime/internal.odin index 71ad9386a..ad8a40acf 100644 --- a/core/runtime/internal.odin +++ b/core/runtime/internal.odin @@ -566,16 +566,37 @@ max_f64 :: #force_inline proc "contextless" (a, b: f64) -> f64 { } abs_complex32 :: #force_inline proc "contextless" (x: complex32) -> f16 { - r, i := real(x), imag(x) - return f16(intrinsics.sqrt(f32(r*r + i*i))) + p, q := abs(real(x)), abs(imag(x)) + if p < q { + p, q = q, p + } + if p == 0 { + return 0 + } + q = q / p + return p * f16(intrinsics.sqrt(f32(1 + q*q))) } abs_complex64 :: #force_inline proc "contextless" (x: complex64) -> f32 { - r, i := real(x), imag(x) - return intrinsics.sqrt(r*r + i*i) + p, q := abs(real(x)), abs(imag(x)) + if p < q { + p, q = q, p + } + if p == 0 { + return 0 + } + q = q / p + return p * intrinsics.sqrt(1 + q*q) } abs_complex128 :: #force_inline proc "contextless" (x: complex128) -> f64 { - r, i := real(x), imag(x) - return intrinsics.sqrt(r*r + i*i) + p, q := abs(real(x)), abs(imag(x)) + if p < q { + p, q = q, p + } + if p == 0 { + return 0 + } + q = q / p + return p * intrinsics.sqrt(1 + q*q) } abs_quaternion64 :: #force_inline proc "contextless" (x: quaternion64) -> f16 { r, i, j, k := real(x), imag(x), jmag(x), kmag(x) diff --git a/core/runtime/print.odin b/core/runtime/print.odin index 326a29667..732ed9c12 100644 --- a/core/runtime/print.odin +++ b/core/runtime/print.odin @@ -5,7 +5,7 @@ _INTEGER_DIGITS :: "0123456789abcdefghijklmnopqrstuvwxyz" @(private="file") _INTEGER_DIGITS_VAR := _INTEGER_DIGITS -when !ODIN_DISALLOW_RTTI { +when !ODIN_NO_RTTI { print_any_single :: proc "contextless" (arg: any) { x := arg if loc, ok := x.(Source_Code_Location); ok { @@ -234,7 +234,7 @@ print_caller_location :: proc "contextless" (using loc: Source_Code_Location) { } } print_typeid :: proc "contextless" (id: typeid) { - when ODIN_DISALLOW_RTTI { + when ODIN_NO_RTTI { if id == nil { print_string("nil") } else { |