The main problem in this case with the register allocator is that for each virtual register, it maintains a linked list of ranges, sorted by start position. Inserting and removing ranges is `O(1)` so this blows up when splitting large ranges. If I change this data structure from a linked list to an `AvlTree`, it improves `ort-wasm-simd-threaded.jsep.wasm` from 292 seconds to 41 seconds locally. This can likely be optimized more as my patch is a naive implementation. I'm also not sure if this list really needs to be sorted; there are a few places where we depend on it but there might be better ways to handle that. I'll look into that some more.
Bug 1916442 Comment 17 Edit History
Note: The actual edited comment in the bug view page will always show the original commenter’s name and original timestamp.
The main problem in this case with the register allocator is that for each virtual register, it maintains a linked list of ranges, sorted by start position. Inserting and removing ranges is `O(n)` so this blows up when splitting large ranges. If I change this data structure from a linked list to an `AvlTree`, it improves `ort-wasm-simd-threaded.jsep.wasm` from 292 seconds to 41 seconds locally. This can likely be optimized more as my patch is a naive implementation. I'm also not sure if this list really needs to be sorted; there are a few places where we depend on it but there might be better ways to handle that. I'll look into that some more.