when the allocator can extend the block in place, realloc avoids
the overhead of malloc+memcpy+free. the keys are moved to their
new position with memmove and extended regions are cleared.
Co-authored-by: Claude <noreply@anthropic.com>
saves 40% memory (60 -> 36 bytes) for objects with 1-2 instance
variables, which is common for simple value objects like Point(@x, @y).
the trade-off is one extra reallocation when growing from 2 to 4 IVs,
but this is negligible since reallocations are rare compared to lookups.
Co-authored-by: Claude <noreply@anthropic.com>
Replace Karatsuba multiplication (O(n^1.585)) with Toom-3 (O(n^1.465))
for large number multiplication. Toom-3 splits numbers into thirds and
evaluates at 5 points, providing better asymptotic performance.
Threshold is 50 limbs (~1600 bits). For operands below threshold or
highly asymmetric sizes, schoolbook multiplication is used.
Co-authored-by: Claude <noreply@anthropic.com>
Remove automatic downgrade to 16-bit limbs on 32-bit Windows.
Modern compilers (including MSVC) have supported uint64_t for decades.
MRB_NO_MPZ64BIT remains available for constrained platforms.
Adjust BATCH_DIVISOR and BATCH_DIGITS for 16-bit limb compatibility:
- 32-bit limbs: 10^9 (9 digits per batch)
- 16-bit limbs: 10^4 (4 digits per batch)
Co-authored-by: Claude <noreply@anthropic.com>
Add trim() after mpz_set in early return paths to prevent propagation
of inflated sz values. When an mpz_t has sz larger than actual allocated
limbs, copying it without trim causes subsequent operations to read
beyond allocated memory.
Fixed functions:
- mpz_add: when one operand is zero
- mpz_neg: when copying operand
- mpz_mod_2exp: when x < 2^e
Co-authored-by: Claude <noreply@anthropic.com>
Document that this header is for mruby core internal use only and
should not be included in user code or mrbgems. When MRB_USE_CXX_EXCEPTION
is defined, C source files including this header fail to compile.
Add example showing mrb_protect_error() as the recommended alternative.
Co-authored-by: Claude <noreply@anthropic.com>
Use mrb_protect_error API instead of direct MRB_TRY/MRB_CATCH to handle
exceptions in mpz_mul_all_ones and mpz_to_s_dc. This maintains C++
compatibility (issue #6702) while ensuring temporary mpz_t allocations
are properly freed even when exceptions occur.
Co-authored-by: Claude <noreply@anthropic.com>
Remove MRB_TRY/MRB_CATCH exception handling from bigint.c to fix
compilation errors when using mruby-bigint in C++ projects with
MRB_USE_CXX_EXCEPTION enabled.
The exception handling was added for cleanup on error, but it requires
throw.h which doesn't work when a C file is compiled in a C++ context
with C++ exceptions enabled. Accepting potential memory leaks on
exception (rare) is preferable to breaking C++ builds.
Fixes#6702
Co-authored-by: Claude <noreply@anthropic.com>
The JMPNOT-to-JMPIF optimization assumed fail_pos always came from a
4-byte JMPNOT instruction. When a pinned variable is undefined,
NODE_PAT_PIN generates a 3-byte OP_JMP instead, causing fail_pos - 2
to point into the previous instruction and corrupt its operand.
Add a check to verify the instruction at fail_pos - 2 is actually
OP_JMPNOT before modifying it.
Fixes#6701
Co-authored-by: Claude <noreply@anthropic.com>
Replace the two-buffer swap pattern in D&C to_s base case with
in-place division using new mpn_div10_9 function. This eliminates
the q_base scratch buffer and reduces per-iteration overhead.
Compilers optimize the constant division by 10^9 to multiplication
and shift operations for better performance.
Co-authored-by: Claude <noreply@anthropic.com>
Replace per-call lo allocation with depth-indexed lo_stack buffers
that are reused across recursion levels. Each buffer is allocated
on first use at that depth with appropriate size.
This reduces 493 malloc/free calls (5%) and 580KB of memory (2%)
for large number to_s conversions while maintaining performance.
Co-authored-by: Claude <noreply@anthropic.com>
Instead of allocating a separate hi buffer for the upper part of the
split, reuse q5 by shifting it in place after extracting the lower
bits to q5_low.
This eliminates one mpz_t allocation per recursive call:
- Extract q5_low = q5 mod 2^k first (copy lower bits)
- Shift q5 right in place (memmove + mpn_rshift) to get hi
- q5 now serves as hi for the recursive call
Benchmark results (2.4M bit number):
- Memory: -3.5% (5.58MB -> 5.38MB peak heap)
- Instructions: -16.5%
- Speed: unchanged (within measurement noise)
Co-authored-by: Claude <noreply@anthropic.com>
Replace array indexing x.p[i+j] with pointer arithmetic *xp++ in the
hot inner loop of Knuth Algorithm D division. This avoids recalculating
the index i+j on every iteration.
Profiling showed the inner loop accounts for ~80% of udiv execution time,
with the array indexing contributing significant overhead.
Benchmark improvement: ~4% faster (7.80s -> 7.48s for 2.4M bit to_s).
Co-authored-by: Claude <noreply@anthropic.com>
When converting large numbers to strings using D&C algorithm, the
base case extracts digits in batches of 9 (for 32-bit limbs). The
extraction logic: 1 leading digit + 4 pairs (8 digits) = 9 digits.
The pair extraction loop condition `pos >= 2` exits when pos < 2,
but when the remaining batch still has value and pos == 1, that
final digit was being lost and replaced with '0' by the padding loop.
This caused roundtrip failures (x.to_s.to_i != x) for numbers just
above the D&C threshold (1000 digits), where the split boundary
produced a lo part requiring exactly the right number of digits to
trigger this edge case.
Co-authored-by: Claude <noreply@anthropic.com>
mpz_to_s_dc_recur fills in exactly num_digits characters but did not
add a null terminator. This caused valgrind errors when strlen was
called on the resulting string.
Co-authored-by: Claude <noreply@anthropic.com>
Add mpn_add_n, mpn_add, mpn_add_1, mpn_sub_n, mpn_sub, and mpn_sub_1
functions that operate directly on limb arrays, following GMP's mpn
layer design. These functions support in-place operation and return
carry/borrow.
Refactor uadd and usub to use these new mpn functions, simplifying the
code significantly (134 lines deleted, replaced with cleaner mpn calls).
Also update limb_sub to delegate to mpn_sub_n.
Co-authored-by: Claude <noreply@anthropic.com>
Add mpn_rshift and mpn_lshift functions that operate directly on limb
arrays, following GMP's mpn layer design. These functions support
in-place operation and return shifted-out bits.
Refactor urshift and ulshift to use these new mpn functions, simplifying
the code and improving reusability.
Co-authored-by: Claude <noreply@anthropic.com>
Use scratch buffers for q5, r5, and q5_low in the recursive case of
D&C decimal string conversion. These temporaries are only needed
during the computation of hi and lo values, not during the recursive
calls, so they can be safely reused at each recursion level.
This eliminates 3 allocations per recursion level (approximately
log2(digits/1000) levels for large numbers), providing an additional
2-3% performance improvement on top of the base case optimization.
Co-authored-by: Claude <noreply@anthropic.com>
Add dc_to_s_scratch_t structure to preallocate work buffers for the
base case of divide-and-conquer decimal string conversion. This
eliminates repeated malloc/free calls in the inner loop where digits
are extracted 9 at a time.
Previously, each iteration of the base case loop allocated and freed
a quotient buffer. Now the same two buffers are reused with pointer
swapping, reducing allocation overhead by ~10-18% for large numbers.
Co-authored-by: Claude <noreply@anthropic.com>
When mpz_or or mpz_xor copies an operand when the other is zero,
the copied mpz_t may have an inflated sz field (larger than actual
allocated limbs). Add trim() after mpz_set to normalize the size.
This is a follow-up fix to commit 61aa2234d8 which addressed the
same issue in shift operations.
Co-authored-by: Claude <noreply@anthropic.com>
Add trim() calls after mpz_set/mpz_move in shift operations where
actual bit manipulation is skipped:
- mpz_mul_2exp when e==0 (no shift needed)
- mpz_mul_2exp when bs==0 (limb-only shift)
- mpz_div_2exp when e==0 (no shift needed)
- mpz_div_2exp when bs==0 (limb-only shift)
This prevents inflated sz values from propagating through operations,
complementing the earlier fix to urshift/ulshift when n==0.
Co-authored-by: Claude <noreply@anthropic.com>
When shift amount is 0, urshift() and ulshift() called mpz_set() which
copies data without trimming leading zero limbs. This caused bigint
values to have inflated sz fields, making ucmp() comparisons incorrect.
For example, a 256-bit remainder from division could have sz=18 instead
of sz=8 because the divisor had 18 limbs. This made it compare greater
than values with fewer limbs, even when numerically smaller.
The bug also caused memory leaks when the incorrect comparison led to
taking wrong code paths in division, triggering size overflow exceptions
after memory was allocated.
Co-authored-by: Claude <noreply@anthropic.com>
rational_eq_b was using wrong struct fields (p1->numerator/denominator
which access i.num/i.den) for bigint-backed rationals that use b.num/b.den.
Also added missing MRB_TT_BIGINT case to prevent fallthrough to default
case which caused ping-pong recursion between Rational#== and Integer#==.
Co-authored-by: Claude <noreply@anthropic.com>
Add MRB_TRY/MRB_CATCH to ensure local mpz_t variables are freed when
an exception (e.g., RangeError from shift overflow) occurs during
the all-ones multiplication optimization.
Co-authored-by: Claude <noreply@anthropic.com>
Use stack allocation with zero-initialization and MRB_TRY/MRB_CATCH
to ensure heap-allocated mpz_t data is freed even when an exception
occurs during conversion.
Co-authored-by: Claude <noreply@anthropic.com>
The pack_float, pack_double, unpack_float, and unpack_double functions
accessed float/double bytes via a union with uint8_t array, assuming
bytes[0] is always the LSB. This is only true on little-endian hosts.
Fix by using the same bit-shift approach as the integer pack functions
(pack_quad, unpack_quad, etc). Reinterpret float/double as uint32/uint64
and use shifts to extract/assemble bytes in an endian-independent way.
Fixes: #6698 (s390x test failures)
when comparing bigint values with <=> operator, the comparison would
convert both operands to float, losing precision for values > 2^53.
this caused incorrect results like (10^20+1) <=> (10^20+2) returning 0
instead of -1.
add direct bigint comparison paths in cmpnum() to avoid float conversion
when both operands can be handled by mrb_bint_cmp().
Co-authored-by: Claude <noreply@anthropic.com>
use the mathematical identity 10^k = 2^k * 5^k to speed up the
divide-and-conquer decimal string conversion. dividing by 5^k
is faster than dividing by 10^k because 5^k has ~30% fewer bits
(log2(5) ≈ 2.32 vs log2(10) ≈ 3.32). the 2^k component is handled
with fast bit shifts.
benchmarks show 3-8% improvement for large numbers:
- 800K bits: 1.00s -> 0.97s
- 1.6M bits: 3.95s -> 3.84s
- 2.4M bits: 8.79s -> 8.46s
Co-authored-by: Claude <noreply@anthropic.com>
Apply Lemire's small table technique: use a 200-byte lookup table to
convert digit pairs (00-99) instead of computing each digit separately.
Reduces operations from 9 to 5 per 9-digit batch in the base case.
Co-authored-by: Claude <noreply@anthropic.com>
With this PR, I can remove the original task.c in picoruby/picoruby and future development will be much easier.
## Add
### General
- C API functions exported with MRB_API for external integration:
- mrb_execute_proc_synchronously() for synchronous proc execution
- Task control APIs (mrb_create_task, mrb_suspend_task, mrb_resume_task, mrb_terminate_task, mrb_stop_task, mrb_task_value, mrb_task_status)
- Task context management APIs for picoruby-sandbox (mrb_task_init_context, mrb_task_reset_context, mrb_task_proc_set)
- Task.tick class method to get current tick count
- Comprehensive C API documentation with WASM integration examples
### For PicoRuby.wasm
- WASM/Emscripten support: Disable SIGALRM timer when __EMSCRIPTEN__ is defined, as JavaScript handles tick calls via setInterval
- Scheduler lock mechanism to prevent asynchronous task operations during synchronous execution (scheduler_lock counter in mrb_task_state)
- mrb_task_run_once() for single-step execution (event loop integration)
## Fix
### task.c
- Replace MRB_FIBER_TERMINATED with MRB_TASK_STOPPED just for clarity
- Allow suspending DORMANT and WAITING tasks in mrb_task_suspend (See comment in the source)
- Task context initialization by removing dummy callinfo push/pop
*NOTE*
With the dummy callinfo code that I deleted, IRB in PicoRuby ended SEGV.
If that code is mandatory, we need to discuss how to solve my problem.
### vm.c
- Handle MRB_TASK_CREATED status in VM's NORMAL_RETURN phase to properly stop tasks
----
These changes are necessary to make PicoRuby work.
Nevertheless, even with this patch, MicroRuby for Raspberry Pi Pico 2 is still unstable.
I would like to merge this PR anyway to make development easier by involving the PicoRuby community.
Follow the codebase convention of using _recur suffix for recursive
functions (e.g., codedump_recur, dump_recur).
Co-authored-by: Claude <noreply@anthropic.com>
Extract 9 decimal digits at once by dividing by 10^9 instead of 10.
This reduces the number of divisions in the base case by 9x, improving
performance of large bigint to_s conversion by approximately 2x.
Co-authored-by: Claude <noreply@anthropic.com>
For base-10 conversion of numbers with >1000 digits, use a recursive
divide-and-conquer algorithm that splits the number using precomputed
powers of 10. This reduces complexity from O(n^2) to O(n log^2 n).
The algorithm:
1. Precompute 10^1, 10^2, 10^4, 10^8, ... by repeated squaring
2. Find the largest power that splits digits roughly in half
3. Divide by this power to get high and low parts
4. Recursively convert each part, padding low part with zeros
5. Base case: use simple divide-by-10 for <= 1000 digits
Co-authored-by: Claude <noreply@anthropic.com>
The final carry was stored at z->p[y->sz], but when x is larger
than y, this index falls within the already-computed result and
corrupts it. Store at z->p[i] instead, which correctly points to
max(x->sz, y->sz) after all loops complete.
This bug caused incorrect results when adding a small number to
an all-ones number with 1124+ limbs (35968+ bits).
Co-authored-by: Claude <noreply@anthropic.com>
The udiv function had two buggy modifications to Knuth's Algorithm D:
1. A "three-limb pre-adjustment" that only decremented qhat once
2. A "3-limb refinement" loop with incorrect carry handling
These caused incorrect quotients for certain decimal divisions like
10^52 / 10^26. Restored standard Knuth Algorithm D which uses only
2-limb qhat refinement with correction via subtract and add-back.
Co-authored-by: Claude <noreply@anthropic.com>
Numbers with few bits set (popcount <= 8) are multiplied using
shift-add instead of Karatsuba. This is O(k*n) where k is the
popcount, much faster than O(n^1.585) for sparse patterns like
2^100000 + 2^50000 commonly generated by fuzzers.
Co-authored-by: Claude <noreply@anthropic.com>
Add optimized squaring algorithm that exploits symmetry for ~1.5x speedup
over general multiplication. Includes both schoolbook and Karatsuba variants.
- mpz_sqr_basic_limbs: O(n(n+1)/2) multiplications instead of O(n^2)
- mpz_sqr_karatsuba: 3 recursive squarings instead of 3 multiplications
- mpz_sqr: high-level wrapper with fast paths for power-of-2 and all-ones
The optimization triggers when mpz_mul is called with identical pointers
(u == v), which occurs in internal operations like mpz_pow.
Co-authored-by: Claude <noreply@anthropic.com>
Add fast path for multiplying by powers of 2 (2^n). Uses left shift
instead of Karatsuba multiplication: x * 2^n = x << n.
This optimizes "mostly-zero" patterns common in fuzzing tests, where
numbers like 2^2097150 (single bit set) would otherwise trigger slow
Karatsuba multiplication.
Co-authored-by: Claude <noreply@anthropic.com>
Add fast path for multiplying numbers of form 2^n - 1 (all bits set).
Uses algebraic identities:
- (2^n - 1) * (2^m - 1) = 2^(n+m) - 2^n - 2^m + 1
- (2^n - 1) * y = (y << n) - y
These are O(n) operations instead of O(n^1.585) for Karatsuba.
Fuzzing test cases using all-ones patterns now complete in 0.01s
instead of 13+ seconds.
Also raises KARATSUBA_THRESHOLD from 8 to 32 for ~32% speedup
on general large number multiplication.
Co-authored-by: Claude <noreply@anthropic.com>
Reduces recursion overhead for large number multiplication.
Benchmarks show ~32% speedup for million-bit operands.
Co-authored-by: Claude <noreply@anthropic.com>
Add MRB_BIGINT_BIT_LIMIT (1 billion bits / 128MB) to prevent
unreasonably large allocations when left-shifting by huge amounts.
Raises RangeError instead of attempting multi-GB allocations.
Co-authored-by: Claude <noreply@anthropic.com>
mpz_and, mpz_or, and mpz_xor were not calling trim() on their results,
causing inflated size values with trailing zero limbs. This led to
incorrect comparisons in ucmp() and caused udiv() to take wrong code
paths, resulting in memory leaks when exceptions occurred.
Also added defensive overflow checks in mpz_init_heap and udiv.
Co-authored-by: Claude <noreply@anthropic.com>
Yukihiro "Matz" Matsumoto