Skip to content

Proposal: Switch wave from bool[][] to bitset for massive speedups #104

@list3ner

Description

@list3ner

Currently WFC tracks allowed patterns per cell using bool[][] wave.

Switching this to a bitset (ulong[], dynamically sized based on T) would:

  • Cut memory by 8 - 10x
  • Remove branchy per-pattern loops
  • Give us hardware accelerated popcount for free
  • Scale cleanly
  • Unlock SMD / perhaps multithread optimizations long-term

This change keeps the API + behavior identical -- it's just a low-level data layout upgrade.

I have more or less drop-in replacement prototype.

For example with only single generation like this:

<overlapping name="Town" N="3" periodic="True" heuristic="MRV" size="300" screenshots="1"/>

Change is significant, without bitset my computer takes 60830ms vs 18092ms using updated data layout and bitset.

Generally what I've noticed with smaller map sizes the performance is identical or marginally better but with increasing sizes of maps it gets significantly faster.

Note: Not sure has anyone tested this in greater details before and found some reasons why it is not working so far I'm seeing improvements but as I haven't done extensive testing there still might be caveats.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions