Help optimizing Aztecs - an ECS now using sparse sets

matthunz · April 13, 2025, 10:16pm

Hey I’ve been working on getting mutable sparse sets (based on vectors) working as the backing data structure for Aztecs GitHub - aztecs-hs/aztecs: A modular game engine and ECS for Haskell.

I’m really struggling getting closer to other ECS frameworks like Apecs, Bevy, or Flecs. I totally accept Haskell may bring some overhead, especially when mimicking the imperative style of a Rust or C++ ECS, but I feel like my current results have to include some low-hanging fruit… I’d absolutely love any help making this ECS faster!

The new sparse set data structure is heavily based off EnTT and Bevy’s versions GitHub - aztecs-hs/sparse-set: An efficient sparse-set data structure for Haskell. At the lower level, this is based on GitHub - aztecs-hs/sparse-vector: Sparse n-dimensional vectors for Haskell, which is basically just a Vector (Maybe a) that provides an API similar to IntMap.

I’ve been able to get queries for 10,000 entities (with two components) down to about 700us on my machine, where the previous immutable IntMap solution was about 100us. Bevy is still blowing this out of the water at about 8us

github.com/aztecs-hs/aztecs

bench/Bench.hs

81e7192ed


      
          import Control.Monad.Primitive
          import Control.Monad.ST
          import Criterion.Main
          import qualified Data.SparseSet as S
          import GHC.Generics
          
          newtype Position = Position Int deriving (Generic, NFData)
          
          newtype Velocity = Velocity Int
          
          move ::
            ( MonadEntities m,
              MonadQuery (ComponentRef (PrimState m) Position) m,
              MonadQuery (ComponentRef (PrimState m) Velocity) m,
              PrimMonad m
            ) =>
            m ()
          move = do
            q <- runQuery $ (,) <$> query <*> query
            mapM_ go q
            where

Bodigrim · April 13, 2025, 11:06pm

I’m afraid Vector (Maybe a) is doomed to be slow. For performance you want to replace Maybe a with (Bool, a), so that you have a bit vector and then Vector a, potentially unboxed if a allows it.

meooow · April 14, 2025, 2:49am

Do you mean MVector?
You don’t mention what operations you use, but with a Vector modifications will be slow, unsurprisingly, because it needs to copy all the elements into a new Vector.

simon · April 14, 2025, 7:12am

You can look at my code here for inspiration (or simply copy it):

I think my code should be reasonably fast. Keep in mind that the Storable version is simply the best for performance. You will never beat it with a boxed approach.