| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This commit polishes the new proc introduced by d9ed816b10a6.
Changes:
- Rename to `toDeque` for more consistency with well-known procs like
`toHashSet` and `toTable`.
- Rename the `openArray` parameter. The name `arr` was potentially less
clear given that the proc can be used with a seq (or string).
- Add a `since` annotation.
- Reword the doc comment, and clarify that ordering is preserved.
- Add runnableExamples.
- Add "see also" cross linking between `initDeque` and `toDeque`.
- Remove duplicate `nextPowerOfTwo`. The `initImpl` template already
includes it.
- Implement the proc using the `items` iterator, rather than indexing.
This matches the implementation of `sets.toHashSet` and
`tables.toTable`.
- Add a test within `when isMainModule`.
- Add a changelog entry.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
* Add ability to initialize a deque with a sequence
Example:
var dq = initDeque[char](@['a', 'b', 'c'])
* Update deques.nim
* Optimized deque initialization
* Sequence replaced by open array in deque initialization
|
| |
|
| |
It needs to have len defined first because of the assert .len > 0. I just moved it up a bit to make them work.
|
| |
|
|
|
|
|
| |
* fix #14139
* Update lib/pure/collections/heapqueue.nim
Co-authored-by: Andreas Rumpf <rumpf_a@web.de>
Co-authored-by: Clyybber <darkmine956@gmail.com>
|
| |
|
|
|
|
|
| |
(#15108)
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.)
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
(#15104)
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.
|
| | |
|
| | |
|
| |
|
|
|
|
|
| |
* Fix #14994
* Revert misplaced "optimization"
* Typo
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* remove a condition that table size must be passed as power of 2
* remove power-of-2 condition from sets and sharedtables
* remove power-of-2 condition from deques
* use 'correctSize' for both branches
* prettify changelog.md and fix typos
* add a changelog entry
* fix double-call of 'right-size'
* fix the same thing in sets.nim
* introduce a new internal proc `slotsNeeded`
Deprecate the public proc `rightSize`, which is not needed anymore.
Now it is an identity function, allowing the old code to work
correctly and without extra allocations.
|
| |
|
|
|
|
|
|
|
|
| |
The `smallest` and `largest` procs for `CountTable` returned a tuple
with named fields, but the same procs for `CountTableRef` returned an
anonymous tuple.
This commit makes those `CountTableRef` procs more consistent, and adds
a test.
Fixes: #14918
|
| | |
|
| |
|
| |
Co-authored-by: Andreas Rumpf <rumpf_a@web.de>
|
| |
|
|
|
|
|
| |
* update to the latest Jester
* remove deprecated procs from some stdlib modules
* 'criterion' is not maintained anymore and relies on obsolete stuff
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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/13393
https://github.com/nim-lang/Nim/pull/13418
https://github.com/nim-lang/Nim/pull/13440
https://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.
* Add neglected API call `find` to heapqueue.
* Add a changelog.md entry, `since` annotation and rename parameter to be
`heap` like all the other procs for consistency.
* Add missing import.
|
| |
|
|
|
| |
* move json.isMainModule => tjson
* move isMainModule => tos,tsequtils
|
| | |
|
| | |
|
| |
|
|
| |
* move since from inclrtl to std/private/since
* move since import in system below for HCR
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
* Error -> Defect for defects
The distinction between Error and Defect is subjective,
context-dependent and somewhat arbitrary, so when looking at an
exception, it's hard to guess what it is - this happens often when
looking at a `raises` list _without_ opening the corresponding
definition and digging through layers of inheritance.
With the help of a little consistency in naming, it's at least possible
to start disentangling the two error types and the standard lib can set
a good example here.
|
| |
|
|
|
|
|
| |
* Add critbits.commonPrefixLen
* add inline and since annotations, as well as a changelog entry
Co-authored-by: Andreas Rumpf <rumpf_a@web.de>
|
| |
|
|
|
|
|
| |
* Add deques.peekFirst/Last(var Deque[T]) -> var T
* Add changelog entry for deques.peekFirst/Last var T overloads
* Add since annotation to peekFirst/peekLast
Co-authored-by: Andreas Rumpf <rumpf_a@web.de>
|
| |
|
|
|
|
|
|
|
|
|
|
| |
* fix mapIt issues #12625 & #12639:
1. fallback to call `map` when the result of `op` is a closure;
2. use `items(s)` in the for loop.
* fix test errors.
* add comments and InType is moved.
* fix ident.
|
| |
|
|
|
| |
* doc: critbit: add runnableExamples
* doc: critbit: change to upper
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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/13393
https://github.com/nim-lang/Nim/pull/13418
https://github.com/nim-lang/Nim/pull/13440
https://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.
* This is an alternate resolution to https://github.com/nim-lang/Nim/issues/13393
(which arguably could be resolved outside the stdlib).
Add version1 of Wang Yi's hash specialized to 8 byte integers. This gives
simple help to users having trouble with overly colliding hash(key)s. I.e.,
A) `import hashes; proc hash(x: myInt): Hash = hashWangYi1(int(x))`
in the instantiation context of a `HashSet` or `Table`
or
B) more globally, compile with `nim c -d:hashWangYi1`.
No hash can be all things to all use cases, but this one is A) vetted to
scramble well by the SMHasher test suite (a necessarily limited but far
more thorough test than prior proposals here), B) only a few ALU ops on
many common CPUs, and C) possesses an easy via "grade school multi-digit
multiplication" fall back for weaker deployment contexts.
Some people might want to stampede ahead unbridled, but my view is that a
good plan is to
A) include this in the stdlib for a release or three to let people try it
on various key sets nim-core could realistically never access/test
(maybe mentioning it in the changelog so people actually try it out),
B) have them report problems (if any),
C) if all seems good, make the stdlib more novice friendly by adding
`hashIdentity(x)=x` and changing the default `hash() = hashWangYi1`
with some `when defined` rearranging so users can `-d:hashIdentity`
if they want the old behavior back.
This plan is compatible with any number of competing integer hashes if
people want to add them. I would strongly recommend they all *at least*
pass the SMHasher suite since the idea here is to become more friendly to
novices who do not generally understand hashing failure modes.
* Re-organize to work around `when nimvm` limitations; Add some tests; Add
a changelog.md entry.
* Add less than 64-bit CPU when fork.
* Fix decl instead of call typo.
* First attempt at fixing range error on 32-bit platforms; Still do the
arithmetic in doubled up 64-bit, but truncate the hash to the lower
32-bits, but then still return `uint64` to be the same. So, type
correct but truncated hash value. Update `thashes.nim` as well.
* A second try at making 32-bit mode CI work.
* Use a more systematic identifier convention than Wang Yi's code.
* Fix test that was wrong for as long as `toHashSet` used `rightSize` (a
very long time, I think). `$a`/`$b` depend on iteration order which
varies with table range reduced hash order which varies with range for
some `hash()`. With 3 elements, 3!=6 is small and we've just gotten
lucky with past experimental `hash()` changes. An alternate fix here
would be to not stringify but use the HashSet operators, but it is not
clear that doesn't alter the "spirit" of the test.
* Fix another stringified test depending upon hash order.
* Oops - revert the string-keyed test.
* Fix another stringify test depending on hash order.
* Add a better than always zero `defined(js)` branch.
* It turns out to be easy to just work all in `BigInt` inside JS and thus
guarantee the same low order bits of output hashes (for `isSafeInteger`
input numbers). Since `hashWangYi1` output bits are equally random in
all their bits, this means that tables will be safely scrambled for table
sizes up to 2**32 or 4 gigaentries which is probably fine, as long as the
integer keys are all < 2**53 (also likely fine). (I'm unsure why the
infidelity with C/C++ back ends cut off is 32, not 53 bits.)
Since HashSet & Table only use the low order bits, a quick corollary of
this is that `$` on most int-keyed sets/tables will be the same in all
the various back ends which seems a nice-to-have trait.
* These string hash tests fail for me locally. Maybe this is what causes
the CI hang for testament pcat collections?
* Oops. That failure was from me manually patching string hash in hashes. Revert.
* Import more test improvements from https://github.com/nim-lang/Nim/pull/13410
* Fix bug where I swapped order when reverting the test. Ack.
* Oh, just accept either order like more and more hash tests.
* Iterate in the same order.
* `return` inside `emit` made us skip `popFrame` causing weird troubles.
* Oops - do Windows branch also.
* `nimV1hash` -> multiply-mnemonic, type-scoped `nimIntHash1` (mnemonic
resolutions are "1 == identity", 1 for Nim Version 1, 1 for
first/simplest/fastest in a series of possibilities. Should be very
easy to remember.)
* Re-organize `when nimvm` logic to be a strict `when`-`else`.
* Merge other changes.
* Lift constants to a common area.
* Fall back to identity hash when `BigInt` is unavailable.
* Increase timeout slightly (probably just real-time perturbation of CI
system performance).
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
(#13816)
* 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/13393
https://github.com/nim-lang/Nim/pull/13418
https://github.com/nim-lang/Nim/pull/13440
https://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.
|
| |
|
|
| |
* Add more Docs and runnableExamples
|
| | |
|
| |
|
|
| |
(#13684)
|
| | |
|
| |
|
|
| |
* fix #13310, Deque misbehaves on VM
* use 'when nimVM'
|
| |
|
|
|
|
|
|
|
|
|
| |
tests (#13498) [backport]
* 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
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
| |
* remove outplace version of 'merge' for CountTables
* remove 'merge' tests
|
| |
|
| |
It didn't work, and it was an oversight to be included in v1.0.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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>
|
| |
|
| |
Correctly remove a key from CountTable when it is set to zero.
|
| | |
|
| | |
|
| | |
|
| | |
|