Negando el truthiness de una evaluación booleana causando 5x desaceleración?

Question

Estoy tratando de implementar un octree, y para eso, necesito un algoritmo de intersección de rayos AABB rápido. Después de buscar, me encontré con este documento que parecía ofrecer ese. A partir del código fuente, disponibles href="http://jgt.akpeters.com/papers/MahovskyWyvill04/" aquí , traduje la función pluecker_cls_cff a C # como esta:

public bool Intersect_2(ref RayPluecker r)
{
  switch (r.Classification)
  {

    // 7 same-ish cases snipped

    case Classification.PPP:

      return !((r.Position.X > this.Max.X) || (r.Position.Y > this.Max.Y) || (r.Position.Z > this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X < 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z > 0));
  }

  return false;
}

Esto parece muy bien el trabajo, pero parecía bastante lento para mí (250 ms a hacer 10 millones que intersecta) así que traté de algunos micro-evaluación de resultados con diferentes variedades. En uno, quité la negación que es justo después de la declaración return y revirtió todas las comparaciones (> a < y viceversa).

Es ahora:

case Classification.PPP:

      return ((r.Position.X < this.Max.X) || (r.Position.Y < this.Max.Y) || (r.Position.Z < this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X > 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z < 0));

Esto debería dar el mismo resultado, ¿verdad? Parecía así, ya que devuelve los mismos resultados que la versión negada con un par de casos de prueba. Sin embargo, en el punto de referencia, que era 5 veces más rápido (50 ms que hacer 10 millones que intersecta)! Estoy seguro de que no se está optimizando cabo, mi criterio es similar al siguiente:

for (int i = 0; i < 10000000; i++)
{
  if (!box.Intersect_3(ref ray))
  {
    throw new Exception();
  }
}

¿Qué puede explicar esta gran diferencia? Estoy corriendo .NET 4.0 en x86.

Answer 1

Su segundo código no hace lo mismo que el primero.

Además de los cambios que ya se ha realizado, que necesita para convertir todos sus RUP en AND. (Véase Leyes de De Morgan .)

apuesto a que después de realizar la revisión, sus dos versiones funcionarán a la misma velocidad.

Answer 2

En concreto relacionado con el rendimiento, apuesto a la instrucción de retorno se cortocircuitos más pronto en el segundo caso que el primero. Puede valer la pena intentar cambiar el orden de las comparaciones si algunos son más propensos que otros a ser verdad. Si cambia los cálculos para que sea equivalente usando && en lugar de || en el segundo caso, a continuación, le gustaría que los que tienen más probabilidades de ser falso con lo primero.