See if use of vectors can improve performance of listy code
#165 opened on Dec 10, 2017
Repository metrics
- Stars
- (201 stars)
- PR merge metrics
- (Avg merge 21m) (1 merged PR in 30d)
Description
There's quite a bit of very core code in dejafu which is using lists in a known-bad way: lots of appending, iteration, and updates. The findBacktrackSteps function is a representative example: https://github.com/barrucadu/dejafu/blob/8c2bf9d78417537ebccd8e7f8d958d07e1514485/dejafu/Test/DejaFu/SCT/Internal.hs#L225-L284
In every iteration, it computes bs ++ [this] and reverse $ zip [0..] bs (both bad) and passes this bs list, indirectly, to pBacktrack which computes reverse (take (i-1) bs), and to backtrackAt, which updates-by-index one or two points towards the end of that list. These are all cases which lists are terrible for!
I wonder if using vectors here would be a performance boost. go could be replaced with a list fold over the function parameters to construct an initial bs, followed by a vector map-with-index over that; the list-comprehension-over-reversed-list in doBacktrack would just be a vector fold-right-with-index, as would the recursion in pBacktrack; and backtrackAt would just use vector update.