Skip to content

faebryk: Core: Better Mifs split path algo#523

Merged
mawildoer merged 17 commits intomainfrom
feature/core_mifs_split_paths
Feb 11, 2025
Merged

faebryk: Core: Better Mifs split path algo#523
mawildoer merged 17 commits intomainfrom
feature/core_mifs_split_paths

Conversation

@iopapamanoglou
Copy link
Contributor

@iopapamanoglou iopapamanoglou commented Nov 16, 2024 •
edited
Loading

faebryk: Core: Improve MIFS split path algo

Description

Current split paths are slow and don't 100% work.
This algo does some smart pruning.
It only looks at a single path in a split at a time.

Current state:

  • Cuts down lots of paths in connected case (see hull i2c)
  • Doesn't seem to make a diff in no connect
  • But that's not a problem (we just want quicker discovery of actual paths so the heuristic limit can be reduced)
  • one open point: pathfinder.cpp ~450: valid but not complete paths should hibernate and be woken up, this can be done in a seperate PR tho
  • Tests all pass
  • cellsim works

image

Demo:

Path(3)[
    *B948.self
    *B948.children
    *B948.lower2.parent]
New split
Split: Path(3)[
    *B948.self
    *B948.children
    *B948.lower1.parent]
Not waiting
Handle valid split branch: Path(10)[
    *B948.self
    *B948.children
    *B948.lower2.parent
    *B948.lower2.self
    *B948.lower2.connected
    *BA18.lower2.connected
    *BA18.lower2.self
    *BA18.lower2.parent
    *BA18.children
    *BA18.self]
Check complete branch for Path(2)[
    *B948.self
    *B948.children]
Wake up path: Path(3)[
    *B948.self
    *B948.children
    *B948.lower1.parent]
Wake signal, checking: 1 paths
Reschedule awoken path: Path(3)[
    *B948.self
    *B948.children
    *B948.lower1.parent]
Handle valid split branch: Path(10)[
    *B948.self
    *B948.children
    *B948.lower1.parent
    *B948.lower1.self
    *B948.lower1.connected
    *BA18.lower1.connected
    *BA18.lower1.self
    *BA18.lower1.parent
    *BA18.children
    *BA18.self]
Check complete branch for Path(2)[
    *B948.self
    *B948.children]
Complete branch found
All branches complete

./test/runpytest.sh -k test_mif_connect_hull

# Before
┏━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━┳━━━━━━━━━┳━━━━━━┳━━━━━━━━┳━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━┳━━━━━━━━━┓
┃ func                 ┃   in ┃ weak in ┃  out ┃   filt ┃ weaker ┃ stronger ┃    time ┃ time/in ┃
┡━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━╇━━━━━━━━━╇━━━━━━╇━━━━━━━━╇━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━╇━━━━━━━━━┩
│ node type            │ 4980 │    4680 │ 3480 │ 30.1 % │      0 │        0 │ 1.33 ms │ 0.27 us │
│ gif type             │ 3480 │    3240 │ 2340 │ 32.8 % │      0 │        0 │ 0.12 ms │ 0.04 us │
│ dead end split       │ 2340 │    2160 │ 2280 │  2.6 % │      0 │        0 │ 0.10 ms │ 0.04 us │
│ conditional link     │ 2280 │    2100 │ 2280 │  0.0 % │      0 │        0 │ 2.06 ms │ 0.90 us │
│ build stack          │ 2280 │    2100 │ 2280 │  0.0 % │    480 │        0 │ 1.70 ms │ 0.75 us │
│ end in self gif      │ 2280 │    2160 │  570 │ 75.0 % │      0 │        0 │ 0.06 ms │ 0.03 us │
│ same end type        │  570 │     540 │   30 │ 94.7 % │      0 │        0 │ 0.13 ms │ 0.23 us │
│ stack                │   30 │       0 │   30 │  0.0 % │      0 │        0 │ 0.00 ms │ 0.05 us │
├──────────────────────┼──────┼─────────┼──────┼────────┼────────┼──────────┼─────────┼─────────┤
│ total                │ 4980 │    4680 │   30 │ 99.4 % │    480 │        0 │ 6.07 ms │ 1.22 us │
│ Total                │      │         │      │        │        │          │ 5.51 ms │ 2.31 us │
└──────────────────────┴──────┴─────────┴──────┴────────┴────────┴──────────┴─────────┴─────────┘


# After
┏━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━┳━━━━━━━━━┳━━━━━━┳━━━━━━━━┳━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━┳━━━━━━━━━┓
┃ func                 ┃   in ┃ weak in ┃  out ┃   filt ┃ weaker ┃ stronger ┃    time ┃ time/in ┃
┡━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━╇━━━━━━━━━╇━━━━━━╇━━━━━━━━╇━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━╇━━━━━━━━━┩
│ node type            │ 2051 │    1751 │ 1329 │ 35.2 % │      0 │        0 │ 0.66 ms │ 0.32 us │
│ gif type             │ 1329 │    1089 │  933 │ 29.8 % │      0 │        0 │ 0.06 ms │ 0.05 us │
│ dead end split       │  933 │     753 │  906 │  2.9 % │      0 │        0 │ 0.05 ms │ 0.06 us │
│ conditional link     │  906 │     726 │  906 │  0.0 % │      0 │        0 │ 0.91 ms │ 1.01 us │
│ build stack          │  906 │     726 │  906 │  0.0 % │    228 │        0 │ 1.94 ms │ 2.14 us │
│ end in self gif      │  906 │     786 │  198 │ 78.1 % │      0 │        0 │ 0.03 ms │ 0.03 us │
│ same end type        │  198 │     168 │   30 │ 84.8 % │      0 │        0 │ 0.06 ms │ 0.29 us │
│ stack                │   30 │       0 │   30 │  0.0 % │      0 │        0 │ 0.00 ms │ 0.04 us │
│ valid split branch   │   30 │       0 │   30 │  0.0 % │      0 │        0 │ 0.00 ms │ 0.04 us │
│ incomplete           │   30 │       0 │   30 │  0.0 % │      0 │        0 │ 0.00 ms │ 0.02 us │
├──────────────────────┼──────┼─────────┼──────┼────────┼────────┼──────────┼─────────┼─────────┤
│ total                │ 2051 │    1751 │   30 │ 98.5 % │    228 │        0 │ 4.00 ms │ 1.95 us │
│ Total                │      │         │      │        │        │          │ 3.72 ms │ 4.00 us │
└──────────────────────┴──────┴─────────┴──────┴────────┴────────┴──────────┴─────────┴─────────┘

@iopapamanoglou iopapamanoglou changed the base branch from main to v0.3.0 November 16, 2024 10:42
@iopapamanoglou iopapamanoglou force-pushed the feature/core_mifs_split_paths branch from be887f4 to 3ab03ef Compare November 16, 2024 10:43
@iopapamanoglou iopapamanoglou mentioned this pull request Nov 16, 2024
Closed
11 tasks
@iopapamanoglou iopapamanoglou marked this pull request as draft November 16, 2024 13:48
@iopapamanoglou iopapamanoglou changed the base branch from v0.3.0 to main November 19, 2024 11:27
@iopapamanoglou iopapamanoglou mentioned this pull request Dec 18, 2024
Closed
1 task
@iopapamanoglou iopapamanoglou marked this pull request as ready for review January 20, 2025 16:13
@mawildoer
Copy link
Contributor

mawildoer commented Jan 20, 2025 •
edited by iopapamanoglou
Loading

TODO:

  • Test against cell-sim w/ more restricted params

mawildoer
mawildoer reviewed Jan 20, 2025
View reviewed changes
Copy link
Contributor

@mawildoer mawildoer left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Unfortunately the builds failing on OXs are pretty stubborn and I'll need your eyes.

I can't seem to force it to use cpp20 here, so it's failing to build based on some cpp17 rules

@iopapamanoglou
Copy link
Contributor Author

iopapamanoglou commented Jan 20, 2025 •
edited
Loading

Unfortunately the builds failing on OXs are pretty stubborn and I'll need your eyes.

I can't seem to force it to use cpp20 here, so it's failing to build based on some cpp17 rules

Done 👍

@iopapamanoglou
Copy link
Contributor Author

iopapamanoglou commented Jan 21, 2025

TODO:

* [ ]  Test against cell-sim w/ more restricted params

Still not working

@iopapamanoglou iopapamanoglou marked this pull request as draft January 21, 2025 11:33
This was referenced Feb 10, 2025
Closed
Merged
@mawildoer mawildoer marked this pull request as ready for review February 11, 2025 20:20
@mawildoer
Copy link
Contributor

mawildoer commented Feb 11, 2025

Results

Before

Screenshot 2025-02-11 at 14 28 29

After

Screenshot 2025-02-11 at 14 28 17

@mawildoer mawildoer enabled auto-merge (squash) February 11, 2025 22:29
@mawildoer mawildoer merged commit e6d48b2 into main Feb 11, 2025
7 of 8 checks passed
@mawildoer mawildoer deleted the feature/core_mifs_split_paths branch February 11, 2025 22:38
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@napowderly napowderly Awaiting requested review from napowderly

1 more reviewer

@mawildoer mawildoer mawildoer approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

regression-required

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@iopapamanoglou @mawildoer