avoid future implementation mischief. (Maybe not. Sometimes, general
distrust of theory leads people to distrust simple reasoning over times
from CPUs trying as hard as possible to mask DRAM latency via pre-fetch.)
(cherry picked from commit 196e747df1)
request. This can be conceived as an alternate, more capable resolution of
https://github.com/nim-lang/Nim/issues/12200
than
https://github.com/nim-lang/Nim/pull/12208
The code re-org idea here is to upgrade tablimpl.nim:`delImpl`/`delImplIdx`
to abstract client code conventions for cell emptiness & cell hashing via
three new template arguments - `makeEmpty`, `cellEmpty`, `cellHash` which
all take a single integer argument and clear a cell, test if clear or
produce the hash of the key stored at that index in `.data[]`.
Then we update the 3 call sites (`Table`, `CountTable`, `SharedTable`) of
`delImpl`/`delImplIdx` by defining define those arguments just before the
first invocation as non-exported templates.
Because `CountTable` does not save hash() outputs as `.hcode`, it needs a
new tableimpl.nim:`delImplNoHCode` which simply in-lines the hash search
when no `.hcode` field is available for "prefix compare" acceleration.
It is conceivable this new template could be used by future variants, such
as one optimized for integer keys where `hash()` and `==` are fast and
`.hcode` is both wasted space & time (though a small change to interfaces
there for a sentinel key meaning "empty" is needed for maximum efficiency).
We also eliminate the old O(n) `proc remove(CountTable...)` in favor of
simply invoking the new `delImpl*` templates and take care to correctly
handle the case where `val` is either zero for non-existent keys in `inc`
or evolves to zero over time in `[]=` or `inc`.
The only user-visible changes from the +-42 delta here are speed, iteration
order post deletes, and relaxing the `Positive` constraint on `val` in
`proc inc` again, as indicated in the `changelog.md` entry.
(cherry picked from commit b2a1944587)
New issue: since `Table[A, B]` allocates its backing storage with
`newSeq[KeyValuePair[A, B]]`, it's no longer legal to create a table
with `not nil` types used as either keys or values.
* Unwind just the "pseudorandom probing" (whole hash-code-keyed variable
stride double hashing) part of recent sets & tables changes (which has
still been causing bugs over a month later (e.g., two days ago
https://github.com/nim-lang/Nim/issues/13794) as well as still having
several "figure this out" implementation question comments in them (see
just diffs of this PR).
This topic has been discussed in many places:
https://github.com/nim-lang/Nim/issues/13393https://github.com/nim-lang/Nim/pull/13418https://github.com/nim-lang/Nim/pull/13440https://github.com/nim-lang/Nim/issues/13794
Alternative/non-mandatory stronger integer hashes (or vice-versa opt-in
identity hashes) are a better solution that is more general (no illusion
of one hard-coded sequence solving all problems) while retaining the
virtues of linear probing such as cache obliviousness and age-less tables
under delete-heavy workloads (still untested after a month of this change).
The only real solution for truly adversarial keys is a hash keyed off of
data unobservable to attackers. That all fits better with a few families
of user-pluggable/define-switchable hashes which can be provided in a
separate PR more about `hashes.nim`.
This PR carefully preserves the better (but still hard coded!) probing
of the `intsets` and other recent fixes like `move` annotations, hash
order invariant tests, `intsets.missingOrExcl` fixing, and the move of
`rightSize` into `hashcommon.nim`.
* Fix `data.len` -> `dataLen` problem.
* fix#13496 handle tombstones
* add test
* more tests
* fix#13504; add SharedTable tests
* fix #https://github.com/nim-lang/Nim/issues/13505 intsets.missingOrExcl silently gave wrong results sometimes
* add test for tintsets
* Add idxmin() which returns the index of the minimum value
* Add idxmax() which returns the index of the maximum value
* Add tests for idxmin()
* Add tests for idxmax()
* Remove initialization of result = 0
* Adds overloading for arrays (no enums indexed arrays yet)
* Add support for enum index arrays
* Fix tests with enum
* Fix tests for idxmax
* Change names of the procedures to minIndex and maxIndex
* address Araq's comments:
- remove 'array' versions
- add .since pragma
- return 'int' instead of 'Natural'
- add changelog entry
Co-authored-by: Federico A. Corazza <20555025+Imperator26@users.noreply.github.com>
https://github.com/nim-lang/Nim/pull/12600
and in
https://forum.nim-lang.org/t/5499
indicates that everyone is happy/happier with ``pop``.
This just renames the brand new ``take``s to ``pop`` and installs inline
aliases/wrappers to preserve ``Table.take`` and ``TableRef.take``.
Update apis.rst to try to maintain consistency of remove-and-return procs.
* cursors: first implementation
* added currently failing test
* .cursor works for doubly linked lists
* make -d:useMalloc work again
* added code to nil out refs in a destructor
* it's now called --gc:arc
* renderer.nim: render nkBreakState properly
* make simple closure iterators work without leaking
* Make sequtils.zip return seq of anonymous tuples
Earlier the tuples had named fields "a" and "b" and that made it
difficult to assign the zip returned seqs to other vars which expected
seqs of tuples with field names other than "a" and "b".
* Make sequtils.zip backwards compatible with Nim 1.0.x
