| Changelog for Judy |
| Release |
What has changed? |
| 2.6.0 |
- FIX: use-after-free during teardown of the MIXED types (INT_TO_MIXED,
STRING_TO_MIXED, STRING_TO_MIXED_HASH, STRING_TO_MIXED_ADAPTIVE), reachable
through both Judy::free() and ordinary object destruction (#162). Freeing a
slot calls zval_ptr_dtor(); where the value is a shared collectable one that
fills the GC root buffer, gc_collect_cycles() then runs synchronously inside
the free loop and re-enters judy_object_get_gc() on the half-destroyed
object. The usual symptom is a "zend_mm_heap corrupted" abort. This defect
PREDATES the bundled libJudy and is present in every previously shipped
release: anyone using a MIXED type should upgrade.
- FIX: libJudy compiled with aggressive loop optimization silently loses
Judy::BITSET keys — jp_1Index is 8 bytes where the code writes up to 15
(#131). Fixed in the bundled tree (patch P1) and guarded by a differential
fuzzer that re-proves itself on every CI run by planting the defect and
failing if the fuzzer does not catch it.
- FIX: further upstream libJudy 1.0.5 defects, fixed in the bundled tree
(#127): the SEARCH_LINEAR/COPYINDEX pair, which was a no-op masking silent
data loss; an off-by-one in InsArray; an out-of-scope read in Cascade; and
hygiene fixes (patches P2-P7). Every patch carries an entry in
libjudy/PATCHES.md and a per-file LGPL section 2(b) change notice.
- BUILD: the bundled, patched libJudy is now the DEFAULT build. ./configure
needs no system library and downloads nothing at build time, and the Windows
build no longer regex-patches library sources in CI. --with-judy=DIR still
links a system libJudy, is CI-tested on every push, and stays supported
indefinitely.
- BUILD: a 32-bit target is now refused with a clear message instead of being
mis-built, and the release matrix is constrained to x64 (#159, #160).
- PERF: integer-keyed paths gain hardware popcount (#149) and a byte-order fix
on the JudyL descend (#150); the string layer loses redundant work (#154).
Figures are in BENCHMARK.md and are deliberately not restated here. Note
that the delivered speedup is NOT one number: with linkage held constant
against an unpatched build of the same tree, about 96.5% of the gain on
integer paths is attributable to these patches but only about 40% of the
gain on string paths, the remainder being static-versus-shared linkage. |
| 2.5.2 |
- PERF: mergeWith() no longer re-descends from the root for a key its own
cursor is already standing on. The slot-to-zval conversion is shared with the
descending read path so the two cannot drift, and the cursor's slot is reused
only where it genuinely holds the value: directly on the integer-keyed and
trie types, and on *_HASH / *_ADAPTIVE only when the payload is mirrored
(an optimizeIteration instance of STRING_TO_INT_HASH, or long-keyed
STRING_TO_INT_ADAPTIVE). Behaviour-preserving: the three new .phpt files pass
against the pre-change build too. **No performance number is claimed** — the
redundant descend is gone, but no benchmark accompanies the change and none
should be inferred pending a run on an idle host. baselines/latest.json and
BENCHMARK.md figures are untouched.
- DOC: API.md now documents that toArray() coerces integer-looking string keys
on string-keyed types ("42" comes back as int 42, while "07" and " 42" stay
strings) and that feeding such a key back as an offset throws. The warning
reached the stub and AGENTS.md in 2.5.1 but not API.md, which is the reference
composer.json advertises.
- DOC: BENCHMARK.md records why php-code-coverage and Infection were examined
and rejected as Judy fits. |
| 2.5.1 |
- FIX: string keys containing an embedded NUL byte are now rejected with an
exception on all six string-keyed types, instead of being silently truncated
at the NUL. Previously STRING_TO_INT and STRING_TO_MIXED truncated the key, so
"ab\0cd" and "ab" collided and one value was destroyed with no signal; the
four *_HASH/*_ADAPTIVE types already rejected such keys on write but still
truncated them on every ordered and range operation (first/last/searchNext/
prev/slice/deleteRange and the bounds of keys/values/toArray/size), because
all six seek through the same JudySL key index. JudySL keys are NUL-terminated
by construction, so rejecting is the only correct behaviour. High-byte keys
(0x80-0xFF) are unaffected and remain binary-safe, including 0xFF prefix-carry
arithmetic. See MIGRATION_2.5.0.md. |
| 2.5.0 |
- BC BREAK: a negative integer offset now stores that key instead of appending.
Integer keys are unsigned machine words, so $j[-1] = $v addresses the maximum
index and reads back as -1. Previously every key in [PHP_INT_MIN, -1] was
discarded and the value appended at the next free index, so isset($j[-1]) was
false immediately after the write. See MIGRATION_2.5.0.md.
- BC BREAK: $j[] = $v now throws when the maximum index is occupied, instead of
wrapping onto index 0 and overwriting it.
- FIX: $j[] = $v no longer loses a value after a negative-offset write left the
append watermark stale
- FIX: map()/filter() preserve negative keys instead of relocating them
- SECURITY: fix use-after-free write on *_TO_MIXED overwrite/unset when a stored
value's destructor re-enters and mutates the same array (write-before-dtor /
delete-before-free)
- SECURITY: fix type confusion (UB) in getAll()/next()/rewind() for adaptive
types, which queried a JudyHS operation against the JudyL (SSO) store
- FIX: add get_gc handler so reference cycles through MIXED values are collectable
(previously leaked until request shutdown)
- FIX: STRING_TO_*_ADAPTIVE counter no longer double-counts when the value 0 is
re-stored (size/count/equals/averageValues were affected)
- FIX: $j[] = append after clone/fromArray/putAll no longer overwrites index 0
- FIX: first()/last()/searchNext()/prev() now work on adaptive types
- FIX: fromArray()/putAll() reject non-integer keys on integer-keyed types instead
of inserting at the string's hash
- FIX: __unserialize() on a populated object frees prior contents (no leak)
- FIX: forEach()/filter()/map() callbacks may re-enter without corrupting iteration
- FIX: equals() on INT_TO_PACKED no longer risks an infinite loop
- FIX: allocation failure (JERR) during write/unset is reported as failure, not success
- FIX: bulk operations stop on the first thrown key instead of continuing with a
pending exception; clone/slice no longer leak zvals or diverge on OOM paths
- FEATURE: keys(), values() and toArray() take an inclusive [$start, $end] key
range, where null leaves that side unbounded. All key types; string-keyed types
require string bounds and compare them lexicographically. A bounded read is one
traversal writing straight into the PHP array — prefer it to slice($lo,
$hi)->keys(), which copies a whole sub-array first.
- FEATURE: size($start, $end) counts that same range, including on the six
string-keyed types, without materialising anything. Previously it accepted
string bounds, ignored them, and returned the whole-array count. Its parameters
were renamed $index_start/$index_end -> $start/$end to match the other range
methods, which breaks named-argument callers only; its defaults moved from
(0, -1) to (null, null). populationCount() is unchanged and stays
integer-keyed-only — it answers from libJudy's O(1) population cache, which the
string-keyed stores lack. See MIGRATION_2.5.0.md.
- FEATURE: new Judy($type, optimizeIteration: true) mirrors payloads into the key
index for 24-47% faster ordered reads, at a write-path and memory cost. Opt-in,
per-instance, off by default, and honoured only by STRING_TO_INT_HASH and
STRING_TO_INT_ADAPTIVE; isIterationOptimized() reports what took effect.
- FEATURE: Judy instances are now legible to debuggers — var_dump()/print_r()
show type, count, memory usage, first/last key and a bounded element preview
(judy.debug_preview_size). Ships lldb/gdb pretty-printers for the extension's
own structs under scripts/.
- FEATURE: set operations (intersect/diff/xor) now supported for STRING_TO_INT_ADAPTIVE
- BUILD: extension compiles warning-free; CI now fails on any new compiler warning
- BUILD: minimum PHP raised to 8.1 (PHP 8.0 is no longer tested in CI) |
| 2.4.2 |
- SECURITY: fix use-after-free write on *_TO_MIXED overwrite/unset when a stored
value's destructor re-enters and mutates the same array (write-before-dtor /
delete-before-free)
- SECURITY: fix type confusion (UB) in getAll()/next()/rewind() for adaptive
types, which queried a JudyHS operation against the JudyL (SSO) store
- FIX: add get_gc handler so reference cycles through MIXED values are collectable
(previously leaked until request shutdown)
- FIX: STRING_TO_*_ADAPTIVE counter no longer double-counts when the value 0 is
re-stored (size/count/equals/averageValues were affected)
- FIX: $j[] = append after clone/fromArray/putAll no longer overwrites index 0
- FIX: first()/last()/searchNext()/prev() now work on adaptive types
- FIX: fromArray()/putAll() reject non-integer keys on integer-keyed types instead
of inserting at the string's hash
- FIX: __unserialize() on a populated object frees prior contents (no leak)
- FIX: forEach()/filter()/map() callbacks may re-enter without corrupting iteration
- FIX: equals() on INT_TO_PACKED no longer risks an infinite loop
- FIX: allocation failure (JERR) during write/unset is reported as failure, not success
- FIX: bulk operations stop on the first thrown key instead of continuing with a
pending exception; clone/slice no longer leak zvals or diverge on OOM paths
- FEATURE: set operations (intersect/diff/xor) now supported for STRING_TO_INT_ADAPTIVE
- BUILD: extension compiles warning-free; CI now fails on any new compiler warning
- BUILD: minimum PHP raised to 8.1 (PHP 8.0 is no longer tested in CI) |
| 2.4.1 |
- FIX: PHP 8.6 build -- XtOffsetOf() alias removed in PHP 8.6.0alpha2; use
standard C offsetof() instead (thanks Remi Collet, PR #65) |
| 2.4.0 |
- NEW FEATURE: Fast ZPP (Zend Parameter Parsing) macros across all methods for improved performance
- NEW FEATURE: Native zend_object_handlers (read/write/has/unset_dimension) bypass ArrayAccess overhead
- NEW FEATURE: Native C iterators via get_iterator for zero-overhead foreach loops
- NEW FEATURE: BITSET set operations -- union(), intersect(), diff(), xor() methods
- NEW FEATURE: INT_TO_INT set operations -- union/intersect/diff/xor with left-wins value semantics
- NEW FEATURE: slice($start, $end) for efficient range extraction on all array types
- NEW FEATURE: JsonSerializable interface -- json_encode() works natively on Judy arrays
- NEW FEATURE: __serialize()/__unserialize() for native PHP serialize/unserialize support
- NEW FEATURE: Batch operations -- fromArray(), toArray(), putAll(), getAll(), increment()
- NEW FEATURE: INT_TO_PACKED type (type 6) -- GC-free opaque value storage via php_var_serialize
- NEW FEATURE: STRING_TO_MIXED_HASH type (type 7) -- JudyHS-backed O(1) string-to-mixed map
- NEW FEATURE: STRING_TO_INT_HASH type (type 8) -- JudyHS-backed O(1) string-to-int map
- NEW FEATURE: STRING_TO_MIXED_ADAPTIVE type (type 9) -- SSO short-string optimization via JudyL
- NEW FEATURE: STRING_TO_INT_ADAPTIVE type (type 10) -- SSO for string-to-int
- NEW FEATURE: .stub.php arginfo generation replaces hand-written C arginfo
- NEW FEATURE: keys(), values() -- native C extraction of keys and values (2-3x faster)
- NEW FEATURE: sumValues(), averageValues() -- C-level aggregation for integer-valued types
- NEW FEATURE: populationCount(start, end) -- range counting via Judy internal population cache
- NEW FEATURE: deleteRange(start, end) -- bulk deletion in a single C pass
- NEW FEATURE: equals(Judy other) -- short-circuit identity comparison
- NEW FEATURE: C-level forEach(), filter(), map() -- bypass PHP Iterator protocol
- NEW FEATURE: String set operations -- union/intersect/diff/xor for STRING_TO_INT and STRING_TO_MIXED types
- NEW FEATURE: mergeWith(Judy $other) -- in-place merge for accumulation patterns (avoids union() allocation)
- FIX: JudySL hang on Windows x64 -- cJU_MASKATSTATE 0xffL truncation at States 5-8 (issue #46)
- FIX: Double-traversal elimination in adaptive types -- removes redundant JLG/JHSG before JLI/JHSI
- FIX: hs_array NULL-check in judy_free_array_internal prevents memory leak in adaptive types
- PERF: JLG+JLI elimination -- 50% fewer tree traversals in write paths for STRING types
- PERF: Branch prediction hints (JUDY_LIKELY/JUDY_UNLIKELY) on hot lookup and validation paths
- PERF: LTO and loop unrolling enabled in compiler flags
- PERF: Memory layout repacked for cache-line alignment and reduced padding
- PERF: Stack safety -- 64KB stack buffers replaced with heap-allocated key_scratch buffer (Fiber-safe)
- PERF: foreach iterator overhaul -- valid flag, heap key buffer, zend_string reuse
- PERF: tagged-union packed format for INT_TO_PACKED -- eliminates serialize for scalars
- PERF: O(1) count() for all types -- counter on every insert/delete replaces O(n) scans
- PERF: type-specialized bulk-insert loops in fromArray()/putAll()/__unserialize()
- PERF: ecalloc to emalloc on 9 zval allocs; direct judy_free_array_internal in __destruct
- IMPROVEMENT: 174 tests covering all features |
| 2.3.0 |
- NEW FEATURE: Windows PECL DLL builds now published with each release (PHP 8.1-8.5, x86/x64, TS/NTS)
- NEW FEATURE: PHP 8.5 support added to CI matrix
- FIX: PHP 8.1+ compile fix - ZVAL_DUP replaced with ZVAL_COPY throughout
- FIX: free_obj memory leak resolved (Judy array, zvals, and iterator state now properly freed)
- FIX: BITSET clone bug fixed (was iterating new array instead of source)
- FIX: STRING_TO_INT counter no longer overcounts on value overwrite
- FIX: E_ERROR replaced with exceptions in constructor and write_dimension
- FIX: foreach-by-ref now throws a proper error instead of E_ERROR; fixed emalloc leak
- FIX: long->zend_long throughout; JLF() iterator bug fixed; redundant JLG lookups removed
- FIX: Removed -march=native and -flto from config.m4 for portability
- IMPROVEMENT: CI workflow consolidated; Windows benchmarks added to CI reporting |
| 2.2.0 |
- **BREAKING CHANGE**: Renamed Judy::next() to Judy::searchNext() to resolve Iterator interface conflicts
- **NEW FEATURE**: Implemented proper Iterator interface support (rewind, valid, current, key, next methods)
- **NEW FEATURE**: Added support for SPL iterators (LimitIterator, FilterIterator, etc.)
- **IMPROVEMENT**: Enhanced benchmark examples with accurate memory measurements
- **IMPROVEMENT**: Updated BENCHMARK.md with comprehensive design explanations and performance analysis
- **IMPROVEMENT**: Added comprehensive benchmark suite with statistical analysis
- **IMPROVEMENT**: Fixed iterator performance analysis and methodology
- **FIX**: All tests now pass (100% success rate)
- **FIX**: Improved memory measurement reliability across different environments
- **FIX**: Fixed critical iterator bugs (next, rewind, valid methods)
- **DOCUMENTATION**: Added O(log n) vs O(1) complexity explanations
- **DOCUMENTATION**: Enhanced benchmark methodology with environment details |
| 2.1.0 |
- Performance improvements for string-keyed arrays through strict key typing (Breaking Change).
- Modernized zval handling for better performance and PHP 8+ compatibility.
- Fixed test suite to accomodate for strict key typing. |
| 2.0.0 |
- Added compatibility for PHP 8.0 and newer.
- Dropped support for PHP versions older than 8.0 (Breaking Change).
- Added a comprehensive benchmark suite (`examples/run-benchmarks.php`) to test realistic workloads.
- Added a `BENCHMARK.md` file with detailed performance results and recommendations.
- Added a `Dockerfile` to provide a consistent development and testing environment.
- Updated `README.md` with modern installation instructions and a link to the benchmark results. |
| 1.0.2 |
- Bug fix with count/size, see https://github.com/orieg/php-judy/issues/15
- Add missing test files in package.xml |
| 1.0.1 |
- Fixes for Windows DDL creation
- Support for PHP 5.5
- Add support for Travis CI
- Update minimum PHP version to 5.3 |
| 1.0.0 |
- First stable release based on 0.1.6 beta |
| 0.1.6 |
- Performance improvement from GitHub pull request #10
- Add countable spl interface from GitHub pull request #9 |
| 0.1.5 |
- Multiple bug fixes and improvment from GitHub pull request #8 |
| 0.1.4 |
- Bug fix foreach with usigned/signed int, see https://github.com/orieg/php-judy/issues/3
- Bug fix segfault with iterator, see https://github.com/orieg/php-judy/issues/2
- Add new test case + fix some ZVAL refcount |
| 0.1.3 |
- Add PHP 5.4 support
- Bug fix count() for STRING_TO_MIXED type, cf. https://github.com/orieg/php-judy/issues/1 |
| 0.1.2 |
- Update examples php code
- Fix Mac OS X support
- Fix infinite loop with foreach() on Windows |
| 0.1.1 |
- Implement array access and iterator to provide access to judy objects as arrays
- Add a judy_type() function and Judy::getType() method
- Remove unused methods, refactor and clean-up some code
- Proper Windows support |
| 0.0.1 |
- Initial PECL release |
|
