FluentCheck: Adding Value Identity Functions To Arbitrary

In the realm of property-based testing with FluentCheck, a proposal has emerged to enhance the Arbitrary class by introducing hashCode and equals value identity functions. This enhancement aims to optimize statistical methods that rely on deterministic object comparison for deduplication, such as sampleUnique. Currently, the deduplication process utilizes JSON.stringify, which presents several performance and memory-related challenges. This article delves into the rationale behind this proposal, the changes it entails, its potential impact, and the open questions that require further investigation.

The Why: Addressing the Limitations of JSON.stringify

The existing approach of using JSON.stringify for object comparison in FluentCheck has several drawbacks that impact performance and memory usage. First and foremost, the serialization cost of O(n) for every comparison is a significant performance bottleneck. This means that for each comparison, the entire object needs to be serialized into a string, which is then immediately discarded. Secondly, the allocation of intermediate strings for each comparison puts unnecessary pressure on memory resources. These strings consume memory and contribute to garbage collection overhead, which can impact the overall performance of the testing process. Thirdly, JSON.stringify is known to fail on objects with circular references, making it unsuitable for testing complex data structures that may contain cycles. Lastly, the non-deterministic nature of object key order in some environments can lead to inconsistent results when using JSON.stringify for comparison. This means that objects with the same properties but in different orders may be considered different, leading to false negatives in deduplication.

For primitive arbitraries like integers and booleans, the overhead of using JSON.stringify is particularly wasteful. Identity comparison for these types is trivial and can be performed much more efficiently using native JavaScript operators. The proposal to introduce hashCode and equals functions aims to address these limitations and provide a more efficient and reliable way to compare objects in FluentCheck.

The What: Introducing hashCode and equals Methods

The proposed changes involve adding two new methods to the Arbitrary<A> class: hashCode() and equals(). These methods will provide a more efficient and deterministic way to compare generated values, enabling O(1) hash-based lookups and improved deduplication performance.

hashCode() Method

The hashCode() method will return a hash function for generated values. Hash functions are essential for implementing hash-based data structures like hash tables and hash sets. By providing a hash function for each arbitrary, FluentCheck can efficiently store and retrieve generated values, enabling O(1) lookups. This is particularly beneficial for deduplication, where we need to quickly check if a value has already been seen. The hash function should be designed to minimize collisions, ensuring that distinct values have different hash codes as much as possible.

equals() Method

The equals() method will return an equality function for deterministic comparison. Equality functions are used to determine if two values are considered equal. In the context of property-based testing, it is crucial to have a deterministic equality function that consistently returns the same result for the same two values. This ensures that deduplication is reliable and that test results are reproducible. The equals() method should implement a deep comparison that takes into account the structure and content of the objects being compared, rather than just their references.

Implementation for Different Arbitraries

The proposal outlines specific implementations for different types of arbitraries:

• Primitive arbitraries (integers, reals, booleans): These arbitraries will implement efficient identity comparison using native JavaScript operators. For example, integers will use strict equality (===), and strings will use native string comparison.
• Constant arbitraries: These arbitraries will use reference equality (===) to compare values, as constants are guaranteed to be the same object instance.
• Composite arbitraries (arrays, tuples, records, sets): These arbitraries will compose identity functions from their element arbitraries. This means that the equality and hash code of a composite object will be determined by the equality and hash codes of its constituent parts. This approach ensures that complex objects are compared based on their content rather than their references.
• Mapped arbitraries: These arbitraries can either inherit identity functions from their base arbitraries or fallback to the default JSON.stringify approach. The choice depends on the mapping function and whether it preserves the identity of the values being mapped.
• Filtered arbitraries: These arbitraries will delegate identity comparison to their base arbitraries, as filtering does not change the underlying values.
• Chained arbitraries: These arbitraries will fallback to the default JSON.stringify approach, as the runtime arbitrary is unknown and it is not possible to derive identity functions statically.

Updating sampleUnique()

The sampleUnique() method will be updated to use the new identity functions for deduplication. This will significantly improve the performance and memory efficiency of sampleUnique(), as it will no longer rely on the costly JSON.stringify approach. The updated sampleUnique() will use the hashCode() method to quickly identify potential duplicates and then use the equals() method to confirm if two values are indeed equal.

The Impact: Performance Gains and Memory Efficiency

The introduction of hashCode and equals methods is expected to have a significant positive impact on the performance and memory efficiency of FluentCheck. By replacing JSON.stringify with more efficient comparison methods, the proposal aims to:

• Reduce the time complexity of deduplication from O(n) to O(1) for hash-based lookups. This will significantly speed up the sampleUnique() method and other statistical methods that rely on deduplication.
• Reduce memory pressure by eliminating the allocation of intermediate strings for each comparison. This will improve the overall performance of FluentCheck and reduce the risk of memory-related issues.
• Enable testing of objects with circular references. The new identity functions will be able to handle objects with cycles, which was not possible with JSON.stringify.
• Ensure deterministic and consistent comparison results. The new equality functions will provide a reliable way to compare objects, regardless of the environment or object key order.

The affected specs and code include:

• arbitraries (Base Class, Sampling Methods)
• src/arbitraries/Arbitrary.ts - add base methods
• src/arbitraries/ArbitraryInteger.ts - efficient integer identity
• src/arbitraries/ArbitraryReal.ts - efficient real identity
• src/arbitraries/ArbitraryBoolean.ts - trivial boolean identity
• src/arbitraries/ArbitraryConstant.ts - reference equality
• src/arbitraries/ArbitraryArray.ts - composite identity
• src/arbitraries/ArbitraryTuple.ts - composite identity
• src/arbitraries/ArbitraryRecord.ts - composite identity
• src/arbitraries/ArbitrarySet.ts - composite identity
• src/arbitraries/MappedArbitrary.ts - inherit or fallback
• src/arbitraries/FilteredArbitrary.ts - delegate to base
• src/arbitraries/ChainedArbitrary.ts - fallback (unknown runtime arbitrary)

Non-Goals: Defining the Scope

The proposal explicitly defines several non-goals to clarify its scope and avoid unnecessary complexity:

• Not providing a user-facing hash/equals API: The hashCode and equals methods are intended for internal optimization purposes and will not be exposed to users directly.
• Not guaranteeing hash collision-free behavior: The hash codes generated by the hashCode method are hints and may not be unique for all values. The equals method is the authoritative way to determine if two values are equal.
• Not supporting custom comparators per-instance: Arbitraries will define their own identity functions, and there will be no support for providing custom comparators on a per-instance basis.

Open Questions: Spikes for Further Investigation

Before implementing the proposed changes, several open questions need to be addressed through small spikes. These spikes will help to measure the impact of different design decisions and ensure that the final implementation is optimal.

Spike 1: Hash Type Performance

Question: Should hashCode return number or bigint?

Test: Benchmark hash-bucketed deduplication with 10K/100K samples using both types.

Measure: Time to deduplicate, memory overhead, collision rate.

This spike will investigate the performance implications of using different hash types. JavaScript's number type has a limited range, which may lead to collisions for large or complex objects. bigint provides a wider range but may have performance overhead. The spike will measure the trade-offs between these two types and determine which is most suitable for hashCode.

Spike 2: Hash Caching in FluentPick

Question: Should we cache hash values in FluentPick?

Test: Run sampleUnique with repeated lookups (shrinking scenarios) with/without caching.

Measure: Memory delta (~8 bytes/pick), time saved on repeated hash calls.

This spike will explore the benefits of caching hash values in FluentPick. Caching can reduce the number of times the hashCode method is called, which can improve performance, especially in scenarios where the same values are compared multiple times, such as during shrinking. However, caching also introduces a memory overhead, as each FluentPick will need to store the hash value. The spike will measure the trade-off between performance gains and memory overhead and determine if caching is worthwhile.

Spike 3: MappedArbitrary Identity Derivation

Question: Should MappedArbitrary always fallback, or optionally derive identity?

Test: Compare mapped arbitrary deduplication with stringify fallback vs optional identity param.

Measure: API complexity, performance gain in common map patterns (e.g., x => x * 2).

This spike will investigate different approaches for handling identity in MappedArbitrary. MappedArbitrary applies a mapping function to the values generated by its base arbitrary. The question is whether MappedArbitrary should always fallback to JSON.stringify for comparison, or if it should optionally derive identity functions from its base arbitrary and the mapping function. Deriving identity functions can improve performance in cases where the mapping function preserves identity (e.g., x => x * 2). However, it also adds complexity to the API. The spike will measure the trade-offs between performance gains and API complexity and determine the best approach for MappedArbitrary.

Conclusion

The proposal to add hashCode and equals value identity functions to the Arbitrary class in FluentCheck is a significant step towards improving the performance and memory efficiency of property-based testing. By replacing JSON.stringify with more efficient comparison methods, this enhancement will enable faster deduplication, reduce memory pressure, and allow for testing of objects with circular references. The open questions identified in this article will be addressed through small spikes, ensuring that the final implementation is optimal. This enhancement promises to make FluentCheck an even more powerful and versatile tool for property-based testing.

For more information on property-based testing and FluentCheck, you can visit the official website of jsverify