Qiskit / qiskit-addon-sqd-hpc / 35352091489

75%

push

github

Use a vendored flat hash map to remove duplicates (#43)

* Use a vendored flat hash map to remove duplicates

The duplicate-removal step in recover_configurations keys an associative
container by the corrected bitstring.  A flat (open-addressed, densely
stored) hash map is considerably faster than std::unordered_map here --
2.3x to 4.2x on the isolated dedup step in benchmarks, widening with the
number of distinct keys -- because it avoids a heap allocation per
distinct key and keeps entries contiguous.  In many workflows duplicates
are rare (correction seldom maps distinct inputs to the same output), so
the map holds close to one entry per input, which is exactly where a flat
map helps most.

To keep the header-only library dependent only on the C++ standard
library for downstream consumers, ankerl::unordered_dense is vendored into
internal/vendor/ rather than required as an external dependency.  Its
top-level namespace and include guards are renamed into project-specific
tokens (via the committed revendor.sh) so that a downstream project which
independently uses its own copy of the library does not collide.  A thin
wrapper, internal/dense_map.hpp, exposes it as internal::dense_map; the
default hash routes through std::hash, which every supported bitstring
type already specializes.

internal/vendor/ is excluded from the clang-format and clang-tidy tox
environments, as it holds third-party code kept as-is.

Assisted-by: Claude Opus 4.8 (1M context)

* Add THIRD_PARTY_NOTICES.md for the vendored unordered_dense

The bundled ankerl::unordered_dense retains its MIT header in each file,
which already satisfies the license.  Add a top-level THIRD_PARTY_NOTICES.md
so the bundled component -- its version, upstream, license text, and the
namespace/guard-rename provenance -- is discoverable in one place for
license audits and SBOM tooling, rather than only by reading the source.
Point the README license note at it.

Assisted-by: Claude Opus 4.8 (1M context)

770 of 1134 branches covered (67.9%)

Branch coverage included in aggregate %.

182 of 266 new or added lines in 2 files covered. (68.42%)

683 of 802 relevant lines covered (85.16%)

304565.66 hits per line