Speedmeasurement with Hall sensors

Hi,
I am using an Arduino Mega with a hall sensor from Tinker! to log the Hall Peaks.
Since logging to a sd-shield was to slow for 2000-4000RPM on the wheel I want to measure, I use the serial-reader OpenLog from Sparkfun.
Afterwards I use MatLab to detect the peaks and to calculate the resulting RPMs, which easily can be transformed to speed.

With one sensor it is quite good (see attached screenshot)
But if I plug in the second sensor, it is terrible (see second screenshot)

I don't just want to average the speeds of two wheels, I also want to log a three-axis g-force and from a GPS-Module the timing- and positioning-information.

To me the Adruino seems to be not fast enough. Is this right or is my sourcecode rubbish?

Thanks for your answers,
Roadrunner

//  ---  SensorShield  ---  //
#define O0 11
#define O1 10
#define O2 9
#define O3 6
#define O4 5
#define O5 3
#define I0 A0
#define I1 A1
#define I2 A2
#define I3 A3
#define I4 A4
#define I5 A5

//Pinbenennung
/*
const int PinGX = I0;  // Analog input pin: G-Sensor
const int PinGY = I1;  // Analog input pin: G-Sensor
const int PinGZ = I2;  // Analog input pin: G-Sensor
*/
const int PinHall1 = I3;  // Analog input pin: Hall-Sensor1
const int PinHall2 = I4;  // Analog input pin: Hall-Sensor2

//Sensorwerte
/*
int ValueGX = 0;        // value var G-Sensor
int ValueGY = 0;        // value var G-Sensor
int ValueGZ = 0;        // value var G-Sensor
*/
int ValueHall1 = 0;        // value var Hall-Sensor
int ValueHall2 = 0;        // value var Hall-Sensor

//Hilfswerte
/*
long LastLogTime = 0;         // saves last timed Logtime
*/
int LastHall1 = 0;        // saves last hall-value
int LastHall2 = 0;        // saves last hall-value

//Loggingabfrage
/*
boolean Loggingtime = 0;        // True, if it is time to log timed sensors
*/
boolean PeakHall1 = 0;        // True, if there is a peak
boolean PeakHall2 = 0;        // True, if there is a peak

void setup(void) {
  // initialize serial communications at 115200 bps (normal 9600 bps)    
  Serial.begin(115200);
  
  delay(10000); // wait for OpenLog to set up
  
  Serial.println("time;Hall1;Hall2");  
  //Serial.println("time;Hall1;Hall2;gX;gY;gZ");
}

void loop() {
  
  //read sensor values
  ValueHall1 = analogRead(PinHall1);  
  ValueHall2 = analogRead(PinHall2); 
  /*
  ValueGX = analogRead(PinGX);  
  ValueGY = analogRead(PinGY); 
  ValueGZ = analogRead(PinGZ);  
  */
  
  //determine, if there is something to log
  if (ValueHall1>500)
    if (ValueHall1<LastHall1)
      PeakHall1=1;
  
  if (ValueHall2>500)
    if (ValueHall2<LastHall2)
      PeakHall2=1;    
  
  /*
  if ((micros()-LastLogTime)>50)
  {
    Loggingtime = 1;
    LastLogTime = micros();
    
    
    if (!PeakHall1 && !PeakHall2)
    {
      Serial.print(micros());
      Serial.print(";");
    }
  }
  */  
  
  
  // log Hall-Sensor values
  
  if (PeakHall1 && !PeakHall2)
  {
    Serial.print(micros());
    Serial.print(";");
    Serial.print(LastHall1);
    Serial.println(";0;");  
  }
  else if (!PeakHall1 && PeakHall2)
  {
    Serial.print(micros());
    Serial.print(";");
    Serial.print("0;");
    Serial.print(LastHall2);
    Serial.println(";");  
  }  
  else if (PeakHall1 && PeakHall2)
  {
    Serial.print(micros());
    Serial.print(";");
    Serial.print(LastHall1);
    Serial.print(";");  
    Serial.print(LastHall2);
    Serial.println(";");  
  }
  
  // log G-Sensor values
  /*
  if (Loggingtime)
  {
      Serial.print(ValueGX);
      Serial.print(";"); 
      Serial.print(ValueGY);
      Serial.print(";"); 
      Serial.print(ValueGZ);
      Serial.print(";");  
  }
  */
  
  // set last values
  LastHall1=ValueHall1;
  LastHall2=ValueHall2;
  
  // reset Bools
  PeakHall1 = 0;
  PeakHall2 = 0;
  /*
  Loggingtime = 0;
  */

}

You are doing a lot of Serial output - this takes time, even at 115200 baud, which may be influencing the readings.
[ also analogRead() takes 110us or so, for two sensors you have to call it twice ]

Why using analog hall sensors? For an RPM sensor a digital output hall sensor is far more appropriate and easy
to interface to.

First, thanks for your answers.

As you might guess, I am new to Arduino. But I need to build a Datalogger for an University-Project.

I need the Serial outputs for the loggingfeature. Would it be more appropriate to buid up a String, which I print in the end?
Is there a more efficient logging method then the SerialLogger or the SD-shield?

About the digital sensors I will try to find more information. Thanks for this hint.