Morph MORPH
SIGN IN SIGN UP
ziglang / zig UNCLAIMED

Moved to Codeberg

0 0 0 Zig
Normal View History Raw
rework std.math.big.Int Now there are 3 types: * std.math.big.int.Const - the memory is immutable, only stores limbs and is_positive - all methods operating on constant data go here * std.math.big.int.Mutable - the memory is mutable, stores capacity in addition to limbs and is_positive - methods here have some Mutable parameters and some Const parameters. These methods expect callers to pre-calculate the amount of resources required, and asserts that the resources are available. * std.math.big.int.Managed - the memory is mutable and additionally stores an allocator. - methods here perform the resource calculations for the programmer. - this is the high level abstraction from before Each of these 3 types can be converted to the other ones. You can see the use case for this in the self-hosted compiler, where we only store limbs, and construct the big ints as needed. This gets rid of the hack where the allocator was optional and the notion of "fixed" versions of the struct. Such things are now modeled with the `big.int.Const` type.
2020-05-01 06:15:58 -04:00
const std = @import("../std.zig");
const assert = std.debug.assert;
rename std lib files to new convention
2019-03-02 16:46:04 -05:00
rework std.math.big.Int Now there are 3 types: * std.math.big.int.Const - the memory is immutable, only stores limbs and is_positive - all methods operating on constant data go here * std.math.big.int.Mutable - the memory is mutable, stores capacity in addition to limbs and is_positive - methods here have some Mutable parameters and some Const parameters. These methods expect callers to pre-calculate the amount of resources required, and asserts that the resources are available. * std.math.big.int.Managed - the memory is mutable and additionally stores an allocator. - methods here perform the resource calculations for the programmer. - this is the high level abstraction from before Each of these 3 types can be converted to the other ones. You can see the use case for this in the self-hosted compiler, where we only store limbs, and construct the big ints as needed. This gets rid of the hack where the allocator was optional and the notion of "fixed" versions of the struct. Such things are now modeled with the `big.int.Const` type.
2020-05-01 06:15:58 -04:00
pub const int = @import("big/int.zig");
pub const Limb = usize;
std: update `std.builtin.Type` fields to follow naming conventions The compiler actually doesn't need any functional changes for this: Sema does reification based on the tag indices of `std.builtin.Type` already! So, no zig1.wasm update is necessary. This change is necessary to disallow name clashes between fields and decls on a type, which is a prerequisite of #9938.
2024-08-28 02:35:53 +01:00
const limb_info = @typeInfo(Limb).int;
big ints: [add|sub]Wrap tests
2021-10-01 15:22:51 +02:00
pub const SignedLimb = std.meta.Int(.signed, limb_info.bits);
Make std.meta.Int accept a signedness parameter
2020-10-17 14:09:59 +02:00
pub const DoubleLimb = std.meta.Int(.unsigned, 2 * limb_info.bits);
std/math: optimize division with divisors less than a half-limb This adds a new path which avoids using compiler_rt generated div udivmod instructions in the case that a divisor is less than half the max usize value. Two half-limb divisions are performed instead which ensures that non-emulated division instructions are actually used. This does not improve the udivmod code which should still be reviewed independently of this issue. Notably this improves the performance of the toString implementation of non-power-of-two bases considerably. Division performance is improved ~1000% based on some coarse testing. The following test code is used to provide a rough comparison between the old vs. new method. ``` const std = @import("std"); const Managed = std.math.big.int.Managed; const allocator = std.heap.c_allocator; fn fib(a: *Managed, n: usize) !void { var b = try Managed.initSet(allocator, 1); defer b.deinit(); var c = try Managed.init(allocator); defer c.deinit(); var i: usize = 0; while (i < n) : (i += 1) { try c.add(a.toConst(), b.toConst()); a.swap(&b); b.swap(&c); } } pub fn main() !void { var a = try Managed.initSet(allocator, 0); defer a.deinit(); try fib(&a, 1_000_000); // Note: Next two lines (and printed digit count) omitted on no-print version. const as = try a.toString(allocator, 10, .lower); defer allocator.free(as); std.debug.print("fib: digit count: {}, limb count: {}\n", .{ as.len, a.limbs.len }); } ``` ``` ==> time.no-print <== limb count: 10849 ________________________________________________________ Executed in 10.60 secs fish external usr time 10.44 secs 0.00 millis 10.44 secs sys time 0.02 secs 1.12 millis 0.02 secs ==> time.old <== fib: digit count: 208988, limb count: 10849 ________________________________________________________ Executed in 22.78 secs fish external usr time 22.43 secs 1.01 millis 22.43 secs sys time 0.03 secs 0.13 millis 0.03 secs ==> time.optimized <== fib: digit count: 208988, limb count: 10849 ________________________________________________________ Executed in 11.59 secs fish external usr time 11.56 secs 1.03 millis 11.56 secs sys time 0.03 secs 0.12 millis 0.03 secs ``` Perf data for non-optimized and optimized, verifying no udivmod is generated by the new code. ``` $ perf report -i perf.data.old --stdio - Total Lost Samples: 0 - - Samples: 90K of event 'cycles:u' - Event count (approx.): 71603695208 - - Overhead Command Shared Object Symbol - ........ ....... ................ ........................................... - 52.97% t t [.] compiler_rt.udivmod.udivmod 45.97% t t [.] std.math.big.int.Mutable.addCarry 0.83% t t [.] main 0.08% t libc-2.33.so [.] __memmove_avx_unaligned_erms 0.08% t t [.] __udivti3 0.03% t [unknown] [k] 0xffffffff9a0010a7 0.02% t t [.] std.math.big.int.Managed.ensureCapacity 0.01% t libc-2.33.so [.] _int_malloc 0.00% t libc-2.33.so [.] __malloc_usable_size 0.00% t libc-2.33.so [.] _int_free 0.00% t t [.] 0x0000000000004a80 0.00% t t [.] std.heap.CAllocator.resize 0.00% t libc-2.33.so [.] _mid_memalign 0.00% t libc-2.33.so [.] sysmalloc 0.00% t libc-2.33.so [.] __posix_memalign 0.00% t t [.] std.heap.CAllocator.alloc 0.00% t ld-2.33.so [.] do_lookup_x $ perf report -i perf.data.optimized --stdio - Total Lost Samples: 0 - - Samples: 46K of event 'cycles:u' - Event count (approx.): 36790112336 - - Overhead Command Shared Object Symbol - ........ ....... ................ ........................................... - 79.98% t t [.] std.math.big.int.Mutable.addCarry 15.14% t t [.] main 4.58% t t [.] std.math.big.int.Managed.ensureCapacity 0.21% t libc-2.33.so [.] __memmove_avx_unaligned_erms 0.05% t [unknown] [k] 0xffffffff9a0010a7 0.02% t libc-2.33.so [.] _int_malloc 0.01% t t [.] std.heap.CAllocator.alloc 0.01% t libc-2.33.so [.] __malloc_usable_size 0.00% t libc-2.33.so [.] systrim.constprop.0 0.00% t libc-2.33.so [.] _mid_memalign 0.00% t t [.] 0x0000000000000c7d 0.00% t libc-2.33.so [.] malloc 0.00% t ld-2.33.so [.] check_match ``` Closes #10630.
2022-02-05 20:36:48 +13:00
pub const HalfLimb = std.meta.Int(.unsigned, limb_info.bits / 2);
Make std.meta.Int accept a signedness parameter
2020-10-17 14:09:59 +02:00
pub const SignedDoubleLimb = std.meta.Int(.signed, 2 * limb_info.bits);
rework std.math.big.Int Now there are 3 types: * std.math.big.int.Const - the memory is immutable, only stores limbs and is_positive - all methods operating on constant data go here * std.math.big.int.Mutable - the memory is mutable, stores capacity in addition to limbs and is_positive - methods here have some Mutable parameters and some Const parameters. These methods expect callers to pre-calculate the amount of resources required, and asserts that the resources are available. * std.math.big.int.Managed - the memory is mutable and additionally stores an allocator. - methods here perform the resource calculations for the programmer. - this is the high level abstraction from before Each of these 3 types can be converted to the other ones. You can see the use case for this in the self-hosted compiler, where we only store limbs, and construct the big ints as needed. This gets rid of the hack where the allocator was optional and the notion of "fixed" versions of the struct. Such things are now modeled with the `big.int.Const` type.
2020-05-01 06:15:58 -04:00
pub const Log2Limb = std.math.Log2Int(Limb);
comptime {
update uses of deprecated type field access
2020-09-03 18:09:55 +03:00
assert(std.math.floorPowerOfTwo(usize, limb_info.bits) == limb_info.bits);
Add builtin.Signedness, use it instead of is_signed
2020-10-17 18:04:53 -06:00
assert(limb_info.signedness == .unsigned);
rework std.math.big.Int Now there are 3 types: * std.math.big.int.Const - the memory is immutable, only stores limbs and is_positive - all methods operating on constant data go here * std.math.big.int.Mutable - the memory is mutable, stores capacity in addition to limbs and is_positive - methods here have some Mutable parameters and some Const parameters. These methods expect callers to pre-calculate the amount of resources required, and asserts that the resources are available. * std.math.big.int.Managed - the memory is mutable and additionally stores an allocator. - methods here perform the resource calculations for the programmer. - this is the high level abstraction from before Each of these 3 types can be converted to the other ones. You can see the use case for this in the self-hosted compiler, where we only store limbs, and construct the big ints as needed. This gets rid of the hack where the allocator was optional and the notion of "fixed" versions of the struct. Such things are now modeled with the `big.int.Const` type.
2020-05-01 06:15:58 -04:00
}
std: Update `test ""` to `test` where it makes sense
2021-01-22 15:45:28 +01:00
test {
rework std.math.big.Int Now there are 3 types: * std.math.big.int.Const - the memory is immutable, only stores limbs and is_positive - all methods operating on constant data go here * std.math.big.int.Mutable - the memory is mutable, stores capacity in addition to limbs and is_positive - methods here have some Mutable parameters and some Const parameters. These methods expect callers to pre-calculate the amount of resources required, and asserts that the resources are available. * std.math.big.int.Managed - the memory is mutable and additionally stores an allocator. - methods here perform the resource calculations for the programmer. - this is the high level abstraction from before Each of these 3 types can be converted to the other ones. You can see the use case for this in the self-hosted compiler, where we only store limbs, and construct the big ints as needed. This gets rid of the hack where the allocator was optional and the notion of "fixed" versions of the struct. Such things are now modeled with the `big.int.Const` type.
2020-05-01 06:15:58 -04:00
_ = int;
_ = Limb;
big ints: [add|sub]Wrap tests
2021-10-01 15:22:51 +02:00
_ = SignedLimb;
rework std.math.big.Int Now there are 3 types: * std.math.big.int.Const - the memory is immutable, only stores limbs and is_positive - all methods operating on constant data go here * std.math.big.int.Mutable - the memory is mutable, stores capacity in addition to limbs and is_positive - methods here have some Mutable parameters and some Const parameters. These methods expect callers to pre-calculate the amount of resources required, and asserts that the resources are available. * std.math.big.int.Managed - the memory is mutable and additionally stores an allocator. - methods here perform the resource calculations for the programmer. - this is the high level abstraction from before Each of these 3 types can be converted to the other ones. You can see the use case for this in the self-hosted compiler, where we only store limbs, and construct the big ints as needed. This gets rid of the hack where the allocator was optional and the notion of "fixed" versions of the struct. Such things are now modeled with the `big.int.Const` type.
2020-05-01 06:15:58 -04:00
_ = DoubleLimb;
_ = SignedDoubleLimb;
_ = Log2Limb;
rename std lib files to new convention
2019-03-02 16:46:04 -05:00
}
Reference in New Issue Copy Permalink