Xe03 Spectrum

So the sprite cache is in, I thought I should tell you all how it works, for the record.

The sprite cache is used to maintain a least recently used list of all the entries so that we can reuse an entry that will have as little impact as possible, the whole point of the sprite cache is to minimise the work done when drawing a sprite.

The main data structure is a doubly linked list that is setup like a queue where we know the top item and the end item. So each time a sprite is rendered it is moved to the top of the queue, then when we need a sprite entry we use the end of the queue.

Now normally a doubly linked list needs to be updated in an operation like moving to the top of the list requires some coniditionals (for updating the head and tail of the list). So in C# (I like to prototype the ideas first and these days C# is the language of choice).

so in this snippet m_cachePrev and m_cacheNext are arrays of ints (pointing at the previous and next entries in the list, First is the first entry in the list and End is the last entry in the list.

        public void MoveToTop( int _index )
        {
            // unhook previous entry
            int prev = m_cachePrev[ _index ];
            int next = m_cacheNext[_index];

            if (next != End)
                m_cachePrev[next] = prev;
            else
                Last = prev;

            if (prev != End)
                m_cacheNext[prev] = next;
            else
                First = next;

            m_cachePrev[_index] = End;
            m_cacheNext[_index] = First;
            m_cachePrev[First] = _index;
            First = _index;
        }

Now on the 6502 because the flags are set on load then Mike can get some benefits and speed ups, so this type of code is fine for Mike, but on the Z80 the flags are not set when an entry is loaded but only after specific operations. So I have been looking for a method of doing this that minimised the branching to make the Z80 code a bit nicer, well my first area of attack was on the First and End entries and the checks that go in there.

So why do we use End as an indicator that this is the start or end of the list? Well just convention really (normally End would be set to NULL) but if End was set to an entry within the array then First and Last could be set to those entries. So I have set End to be the last index of the array and allocate an extra entry (so if we have 128 entries in the cache then the 129th entry becomes the First and Last entries)

First == m_cacheNext[ End ];
Last == m_cachePrev[ End ];

then we can lose the conditionals because the actions would be the same. So the code becomes in C#

            // unhook previous entry
            int prev = m_cachePrev[_index];
            int next = m_cacheNext[_index];

            m_cachePrev[next] = prev;
            m_cacheNext[prev] = next;

            m_cachePrev[_index] = End;
            m_cacheNext[_index] = First;
            m_cachePrev[First] = _index;
            First = _index;

and then in Z80 this becomes

DSO_MoveToTop: 
             ld  h,high sprite_cache_entry_prev
  ld  b,h
  ld  l,c
  ld  e,(hl)       ; e = prev
  ld  (hl),SPRITE_CACHE_END   ; m_cachePrev[_index] = SPRITE_CACHE_END
  ld  h,high sprite_cache_entry_next
  ld  d,h
  ld  c,(hl)       ; c = next
  ld  a,e
  ld  (bc),a       ; m_cachePrev[next] = prev
  ld  a,c
  ld  (de),a       ; m_cacheNext[prev] = next
  ld  e,SPRITE_CACHE_END
  ld  a,(de)       ; a = First
  ld         (hl),a                ; m_cacheNext[_index] = First
  ld  c,a
  ld  a,l
  ld  (bc),a       ; m_cachePrev[First] = _index
  ld  (de),a       ; First = _index

If you spot any optimisations then let me know.