Iterating arrays from right to left might be faster

[sjakobi]

unordered-containers/Data/HashMap/Internal/Array.hs

Lines 382 to 409 in afd8d9b

	foldl' :: (b -> a -> b) -> b -> Array a -> b
	foldl' f = \ z0 ary0 -> go ary0 (length ary0) 0 z0
	where
	go ary n i !z
	| i >= n = z
	| otherwise
	= case index# ary i of
	(# x #) -> go ary n (i+1) (f z x)
	{-# INLINE foldl' #-}
	foldr' :: (a -> b -> b) -> b -> Array a -> b
	foldr' f = \ z0 ary0 -> go ary0 (length ary0 - 1) z0
	where
	go !_ary (-1) z = z
	go !ary i !z
	| (# x #) <- index# ary i
	= go ary (i - 1) (f x z)
	{-# INLINE foldr' #-}
	foldr :: (a -> b -> b) -> b -> Array a -> b
	foldr f = \ z0 ary0 -> go ary0 (length ary0) 0 z0
	where
	go ary n i z
	| i >= n = z
	| otherwise
	= case index# ary i of
	(# x #) -> f x (go ary n (i+1) z)
	{-# INLINE foldr #-}

Important functions like size, toList, foldl' are based on A.foldl' and A.foldr which traverse arrays from left to right, stopping when i >= n.

foldr' on the hand is allowed go right to left and has the benefit of requiring one argument less in its inner loop.

I think we should try to turn things around and see whether we can speed the important functions up by going right to left.

[sjakobi]

(I'd also like to take another look at #373 and check whether ary really needs to be a parameter of these inner go functions.)

[treeowl]

Pulling out a single static argument usually isn't a win, except in those cases where it enables useful inlining.

[sjakobi]

I briefly experimented with foldr' in size, but it seemed to make things slightly worse. I haven't really investigated further.

ddd9047