Passing keys between members/exists and get/set

[dpwiz]

• explGet is currently guarded by explMembers and explExists.
• explSet is obliged to work whenever the component exists or not.

I've been thinking, what if explExists could instead return some key into the store, so explGet would know how to fetch data without traversing the store again?

This could give array-backed stores a boost:

type instance Elem (Buffer a) = a
type instance Key (Buffer a) = Ptr a -- new type family

instance _ => ExplGet m (Store a) where
  explExists :: Store a -> Int -> m (Maybe (Key (Store a)))
  explExists Store{slots} ety =
    liftIO $
      fmap (IntMap.lookup ety) $ -- `lookup` instead `member`, same O(), wraps in Maybe
        readIORef slots

  explGet :: Store a -> Key (Store a) -> m a
  explGet _store key =
    liftIO $
      peek key -- aaand... done.

instance _ => ExplSet (Store a) where
  explSet _store key value =
    liftIO $
      poke key value -- 🎉

instance _ => ExplMembers (Store a) where
  explMembers Store{slots} =
    liftIO $
      fmap (U.fromList . IntMap.toList) $ -- `toList` instead of `keys`, wraps in `(,)` (pairs have `Unbox`).
        readIORef slots

Of course this is all irrelevant for the "pure functional data structures"...

type instance Elem (Buffer a) = a
type instance Key (Map a) = Int -- The entity id is the component key

instance _ => ExplGet (Map a) where
  explExists (Map ref) ety =
    liftIO $
      fmap (bool Nothing (Just ety) . IntMap.member key) $ -- just handling the wrapping
        readIORef ref

  explGet (Map ref) key =
    liftIO $
      flip fmap (M.lookup key <$> readIORef ref) >>= -- not helpful
        maybe notFound pure

instance _ => ExplMembers (Map a) where
  explMembers (Map ref) = 
    liftIO $
      fmap (U.fromList . (\ety -> (ety, ety)) . M.keys) $ -- now this is just embarrassing 😅
        readIORef ref

So, there is a tension between 1) pure structures -- where you can't cut any corners by passing extra data between tests and reads/writes. 2) "unsafe" stores -- where existence witness is necessary and sufficient to go for the data directly.

[dpwiz]

Perhaps this can be resolved with multiple type classes. But the library then should somehow make a choice behind the scenes, deciding which route to pick and keep cmap and its likes unified.

[jonascarpay]

Interesting. I wonder in what cases you could actually get a measurable speed-up with this. For caches, the amount of work shared between a explGet and explExists is minimal, since the tags and elements are kept in different vectors.

Implementation-wise, maybe having a overrideable explSafeGet that returns a Maybe would work, which would have a default implementation based on explExists and expl(Unsafe)Get? Still though, I'd need to see a case in which this would provide a performance benefit. I'm not sure you could, for example, design a faster cache with this.

[dpwiz]

I managed to beat it by a narrow margin using an alternative set of type classes and avoiding cmap. The result is inelegant at best.

You can see the workbench at https://gitlab.com/dpwiz/vecpack. src/Data/Vecpack/* is my store and bench/Worlds/* are competing implementations. (Also, there are Tag benchmarks for unsafe/generic/map/map+filter.)

But the actual goal here is to use a buffer shared with GPU to avoid serialization entirely (the collect, store and slice bench groups). Maybe even run systems on GPU with compute.