JIT executor invalidation needs to be sped up #144888
Description
Feature or enhancement
Proposal:
@chris-eibl has done some benchmarking on Windows for the JIT. It turns out invalidation is actually a massive hot spot and is very slow in bigger programs. The problem is that even if there's only 1 executor actually being invalidated in a list of 100, we have to traverse the entire linked list of 100 anyways. I'll leave it to him to explain his findings more in this issue.
Currently, executor invalidation is a linked list. There are a few ways to fix this. However, I propose we store the bit pattern of the bloom filter in a binary tree. We then do a binary search over the bitpattern in the tree. This will allow us to easily invalidate all the values in O(logn) time, where and n=total executors.
Pinging the usual people @markshannon @reidenong @cocolato for your thoughts. If Mark agrees on this, I'll assign it to @cocolato (assuming you agree to it).
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response