Inefficient bitmap iteration in `filterMapAux.filterA`

[sjakobi]

unordered-containers/Data/HashMap/Internal.hs

Lines 2071 to 2098 in 4da2c20

	filterA ary0 b0 =
	let !n = A.length ary0
	in runST $ do
	mary <- A.new_ n
	step ary0 mary b0 0 0 1 n
	where
	step :: A.Array (HashMap k v1) -> A.MArray s (HashMap k v2)
	-> Bitmap -> Int -> Int -> Bitmap -> Int
	-> ST s (HashMap k v2)
	step !ary !mary !b i !j !bi n
	| i >= n = case j of
	0 -> return Empty
	1 -> do
	ch <- A.read mary 0
	case ch of
	t | isLeafOrCollision t -> return t
	_ -> BitmapIndexed b <$> A.trim mary 1
	_ -> do
	ary2 <- A.trim mary j
	return $! if j == maxChildren
	then Full ary2
	else BitmapIndexed b ary2
	| bi .&. b == 0 = step ary mary b i j (bi `unsafeShiftL` 1) n
	| otherwise = case go (A.index ary i) of
	Empty -> step ary mary (b .&. complement bi) (i+1) j
	(bi `unsafeShiftL` 1) n
	t -> do A.write mary j t
	step ary mary b (i+1) (j+1) (bi `unsafeShiftL` 1) n

• The initial bit mask bi is 1. It would be better to start with the lowest set bit (b0 .&. negate b0).
• On each iteration the bit mask is left-shifted by 1. It would be better to pick the next lowest set bit.