Arduino board - Interrupt Pin rate?

Use direct port manipulation for reading the encoder pins, much faster than digitalRead(), and you should get
quite a speed-up.

You can check pin2 (on an Uno) like this

  if (PIND & 4)

and pin3

  if (PIND & 8)

So something like this will run faster:

void doEncoder_Expanded()
{
  byte b = PIND ;
  if (b & 4)
  {
    if (b & 8)
      enc0 -- ;
    else
      enc0 ++ ;
  }
  else
  {
    if (b & 8)
      enc0 ++ ;
    else
      enc0 -- ;
  }
}

Note the copying of PIND into b - this means that we read the state of pin2 and 3 simultaneously and just once - this
prevents any race conditions.