[MUD-Dev] Re: TECH: Distributed Muds

[Ola Fosheim Grøstad <olag@ifi.uio.no>]

J C Lawrence wrote:

> Translation: You're trying to keep N discrete objets in system
> memory, where the N objects are distributed across M virtual memory
> pages, where M approaches N in the pessimal case.  Given that your
> application is also trying to keep a whole bunch of other things in
> the page cache, as the sum of M + (rest of working set) grows the
> more your VM system will thrash.

So, you should write a dedicated allocator for default sizes and fill
each page with objects of the same size? (Or use a garbage collector).

If you maintain MRU info and count how often the object is among the M
most used objects then you can try to rearrange objects according to
the accesspattern, so they sit on the same pages. Which ought to be
quite easy with N default sizes, only chunks with the same size on
each page and indirect objectaccesses (objID). No absolute need to go
for the explicit disk thing if you are willing to tinker, surely?

Simple is beautiful, but I don't see why people would use linked lists
when they can use a large array for global IDs. Maybe someone could
explain why? Anyway, if trashing is a problem, then you can maintain a
few additional boolean arrays (or bitvector) representing the
important properties you are looking for.

i.e.

  assert( (SIZE%64) == 0 );
  Object *objarr[SIZE];
  uint64 important_property[SIZE/64];

Then scan important_property until you find a set bit. If set bits are
less than approximately 2% then you might even maintain two layers to
speed up scanning. Sketchy:

  assert( (SIZE%(64*64)) == 0 );
  uint64 prop[SIZE/64];
  uint64 nonempty[SIZE/(64*64)];

  bool is_set(ulong i){
    return prop[i/64] & (uint64(1) << (i%64));
  }

  void set(ulong i){
    prop[i/64] |= (uint64(1) << (i%64));
    nonempty[i/(64*64)] |= (uint64(1) << ((i/64)%64));
  }

  void clear(ulong i){
    prop[i/64] &= ~(uint64(1) << (i%64)); 
    if(prop[i/64]) return;
    nonempty[i/(64*64)] ^= (uint64(1) << ((i/64)%64));
  }

With this in place you can scan 4 million objects by switftly passing
over just a thousand 64 bit words which in many cases are likely to be
neglible compared to the time spent accessing "dirty" objects. Of
course, there is a small overhead in the setting and clearing of bits,
and you get a less object oriented program...


--
Ola  -  http://www.notam.uio.no/~olagr/

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev