Hall effect sensors

will be much more accurate because the period will be measured to an accuracy of 62.5 nS.

62.5 ns is true if you use HW timers, if you use micros() the accuracy goes in steps of 4 micros().

Putting all the timing math in the IRQ gives something like this. Note I removed the counter in the IRQ routine to get max update frequency.
Drawback of this method seems to be that you cannot measure an RPM of zero. => additional code needed to check this.
In general low (<60) RPM's will result in a low (> 1s) update frequency ==> more pulses per rotation needed [for every measure method]

//
//    FILE: rpm4.pde
//  AUTHOR: 
//    DATE: 21-oct-2012
//
// PUPROSE: updates rpm after every pulse
//
volatile boolean newRpm = false;
volatile unsigned int rpm = 0;         // assuming not above 65535
volatile unsigned long time = 0;
volatile unsigned long timeold = 0;

void setup()
{
  Serial.begin(115200);
  attachInterrupt(0, rpm_fun, FALLING);
}

void loop()
{
  if (newRpm)
  {
    newRpm = false;
    Serial.print(millis());
    Serial.print(", ");
    Serial.println(rpm);
  }
}

// every pulse a new rpm value, 
void rpm_fun()  
{
  time = micros();
  unsigned long duration = time - timeold;
  rpm = 60000000UL/duration;
  timeold = time;
  newRpm = true;
}