Improve single-threaded performance to the level of our competition

[tameware]

https://github.com/macroxue/bridge-solver is single-threaded C++ and in my initial benchmarking is faster than single-threeaded dds by about 10%.

Its WASM build is also faster than dds, many times faster on some deals, in spite of dds' WASM being multi-threaded.

[tameware]

I wired up dtest and benchmark.py to include bridge-solver. Here are the results for randomly generated hands, on an 18-core M5 Max Mac:

Multithreaded dds vs single-threaded bridge-solver

Summary (avg user ms)
==============================================================================
solver file             benchmark       solver        rel note
------ ------------- ------------ ------------ ---------- ---------------
calc   list1000.txt          6.69        87.84     13.13x benchmark faster
calc   list100.txt           8.58        87.18     10.16x benchmark faster
calc   list10.txt           23.70        64.10      2.70x benchmark faster
calc   list1.txt            58.00       125.00      2.16x benchmark faster
------ ------------- ------------ ------------ ---------- ---------------
TOTAL  calc                  7.06        87.60     12.41x benchmark faster

Single-threaded dds vs single-threaded bridge-solver

Summary (avg user ms)
==============================================================================
solver file             benchmark       solver        rel note
------ ------------- ------------ ------------ ---------- ---------------
calc   list1000.txt         89.14        85.51      0.96x solver faster
calc   list100.txt          80.45        78.95      0.98x solver faster
calc   list10.txt           73.60        60.20      0.82x solver faster
calc   list1.txt           133.00       109.00      0.82x solver faster
------ ------------- ------------ ------------ ---------- ---------------
TOTAL  calc                 88.26        84.71      0.96x solver faster

[tameware]

Here are timings for a "freak" deal. Single-threaded Bridge-solver much faster than multi-threaded dds:

Multithreaded:

% time bazel-bin/utilities/dd_table_for_deal "N:AQT62..Q97.AT832 K85.KJ753..KJ765 9.AT8642.AJ8642. J743.Q9.KT53.Q94"
dd_table_for_deal:
------------------
            AQT62
            -
            Q97
            AT832
J743                    K85
Q9                      KJ753
KT53                    -
Q94                     KJ765
            9
            AT8642
            AJ8642
            -

      North South East  West
   NT     7     7     5     6
    S     8     8     5     5
    H     8     8     5     5
    D    11    11     2     2
    C     6     6     6     7

Par: NS 5D = 400
bazel-bin/utilities/dd_table_for_deal   26.84s user 0.11s system 232% cpu 11.575 total

Single-threaded:

% time bazel-bin/utilities/dd_table_for_deal "N:AQT62..Q97.AT832 K85.KJ753..KJ765 9.AT8642.AJ8642. J743.Q9.KT53.Q94" --numthr 1
dd_table_for_deal:
------------------
            AQT62
            -
            Q97
            AT832
J743                    K85
Q9                      KJ753
KT53                    -
Q94                     KJ765
            9
            AT8642
            AJ8642
            -

      North South East  West
   NT     7     7     5     6
    S     8     8     5     5
    H     8     8     5     5
    D    11    11     2     2
    C     6     6     6     7

Par: NS 5D = 400
bazel-bin/utilities/dd_table_for_deal  --numthr 1  24.20s user 0.07s system 99% cpu 24.296 total

Bridge-solver, always single-threaded:

% time ../bridge-solver/solver -f ../bridge-solver/deals/freak/deal.0
                          ♠ AQT62 ♥ - ♦ Q97 ♣ AT832
  ♠ J743 ♥ Q9 ♦ KT53 ♣ Q94                       ♠ K85 ♥ KJ753 ♦ - ♣ KJ765
                          ♠ 9 ♥ AT8642 ♦ AJ8642 ♣ -
N  7  7  6  5  4.46 s 263392.0 M
S  8  8  5  5  4.79 s 263424.0 M
H  8  8  5  5  5.61 s 263568.0 M
D 11 11  2  2  5.67 s 263568.0 M
C  6  6  7  6  7.11 s 264048.0 M
../bridge-solver/solver -f ../bridge-solver/deals/freak/deal.0  7.07s user 0.04s system 99% cpu 7.124 total

[tameware]

Here's what Cursor had to say about the reasons for the difference:

On freak.0, the gap is real: bridge-solver ~7s single-threaded vs DDS ~25s with --numthr 1 (~12s multi-threaded).

The main reasons:

Shape + pattern transposition (biggest difference)
bridge-solver indexes by hand shape, then stores nested relative-rank patterns with α/β bounds that can match related positions via subset inclusion. That reuses a lot of work on void-heavy / freak deals. DDS’s TT is a more conventional position table — strong, but less generalizing.

One growing cache for the whole DD table
bridge-solver solves all strains in one process and keeps expanding that shared cache, so later strains benefit from earlier search. DDS’s parallel CalcDDtable path uses separate per-worker TTs, so strains don’t share learning. Even sequential DDS only shares a classic TT, not the shape/pattern structure.

Aggressive relative-rank / equivalence pruning
Both prune equivalent cards; bridge-solver builds its cache keys and cutoffs more directly around relative ranks and “rank winners,” which pays off on sparse-suit freak hands.

Hard-tail behavior
On random deals the author claims ~1.5×. On freak/hard tails the gap widens — exactly where shape/pattern reuse matters most. Your deal is in that tail.

So: bridge-solver isn’t magically parallelizing better here; it’s searching less, mainly via a more transferable transposition/pattern model.

[tameware]

Cursor's suggestions for dds:

Highest-impact lessons from bridge-solver, ordered by likely payoff:

1. Shape + pattern transposition (biggest gap)

DDS caches fairly exact positions. bridge-solver indexes by suit-length shape, then stores nested relative-rank patterns whose bounds can match related holdings (subset / generalization).

That is why freak / void-heavy deals diverge so much. A DDS analogue would be a second TT layer: shape key → relative pattern → α/β bounds, not only concrete card keys.

2. Share search memory across the whole DD table

bridge-solver keeps one growing cache for all strains/leads. DDS CalcDDtable often uses separate per-worker contexts, so strains do not teach each other.

Even without new TT math: for hard single deals, prefer one fat sequential/shared TT (or shared TT across strain workers) over five isolated pools. Parallelism helps wall time only when strains are balanced; on freak hands it often does not.

3. Cache more aggressively / grow under pressure

bridge-solver doubles cache size on hard searches (hundreds of MB). DDS’s Large/Small TT model is more fixed. Adaptive growth (or a “hard deal” mode with a much larger TT budget) would help the long tail without taxing easy deals.

4. Stronger relative-rank / “rank winner” cutoffs

DDS already has relative ranks and equivalent-card merge. bridge-solver pushes that into TT keys and early cutoffs (fast/slow trick estimators tied to rank winners). Tightening DDS’s QuickTricks / LaterTricks / TT keys around relative winners is incremental but real.

5. Do not expect threads to close the gap

bridge-solver is single-threaded per deal and still beats multi-threaded DDS on hard hands. The win is fewer nodes, not more cores. Batch multi-deal parallelism (dtest-style) is where threads shine; per-deal 5-strain fanout is not.

Practical roadmap for this repo

1. Prototype a shape/pattern cache beside the existing TT; measure on deals/freak / hard tails.
2. Add a “shared TT for CalcDDtable” path (sequential or shared-store workers).
3. Profile whether current TT capacity is the limiter on freak.0 before rewriting search.
4. Keep multi-deal parallelism; treat per-strain parallelism as optional for easy deals.

Bottom line: the main lesson is more transferable transposition, not better threading.

[tameware]

Adding Shape + pattern transposition from bridge-solver to dds seems to improve both single and multi-threaded performance, single-threaded to better than bridge-solver's. I'll have another look in the morning and submit a PR if the results hold up.

[tameware]

Results no longer hold up. I'll backtrack…

[tameware]

Item 1 is in progress – PR #368