Trouver et corriger les goulots d'étranglement de performance en O(n²) : Leçons tirées des optimisations algorithmiques de Cal.com

Introduction

Les goulets d'étranglement de performance dans les systèmes de planification peuvent faire la différence entre une expérience utilisateur réactive et des utilisateurs quittant votre plateforme par frustration. Chez Cal.com, nous avons récemment découvert et optimisé plusieurs algorithmes critiques O(n²) qui causaient des ralentissements à mesure que notre base d'utilisateurs et nos volumes de données augmentaient.

Dans cet article, je partagerai quatre optimisations réelles d'algorithmes tirées du code de Cal.com. Vous apprendrez comment nous avons détecté la complexité O(n²), quelles stratégies d'optimisation ont le mieux fonctionné, et comment nous avons mis en place des vérifications automatisées pour prévenir les régressions futures.

Le problème : Comment le code innocent devient O(n²)

À mesure que les plateformes de planification grandissent, il est étonnamment facile pour des boucles imbriquées apparemment innocentes de devenir des tueurs de performance silencieux. Considérez cet exemple réel tiré de notre base de code :

// O(n²): Every available slot is checked against every busy period
availableTimeSlots.map(slot => {
  return busy.some(busyTime => checkOverlap(slot, busyTime));
});

// O(n²): Every available slot is checked against every busy period
availableTimeSlots.map(slot => {
  return busy.some(busyTime => checkOverlap(slot, busyTime));
});

// O(n²): Every available slot is checked against every busy period
availableTimeSlots.map(slot => {
  return busy.some(busyTime => checkOverlap(slot, busyTime));
});

Pour 100 créneaux et 50 périodes occupées, cela représente 5 000 vérifications de chevauchement. À plus grande échelle—500 créneaux et 200 périodes occupées—cela explose à 100 000 opérations. C'est une augmentation de charge computationnelle par vingt pour seulement une augmentation par cinq des données.

Étude de cas 1 : Optimisation de la vérification des conflits de créneaux

Le problème initial

La fonction checkForConflicts utilisait une itération imbriquée pour vérifier si des créneaux de réservation entraient en conflit avec des périodes occupées. Cela est devenu rapidement un problème de performance avec des plannings importants.

Implémentation originale : Boucles imbriquées O(n²)

function checkForConflicts({ busy, time, eventLength }) {
  return busy.some(busyTime => {
    const slotStart = time.valueOf();
    const slotEnd = slotStart + eventLength * 60 * 1000;
    const busyStart = dayjs.utc(busyTime.start).valueOf();
    const busyEnd = dayjs.utc(busyTime.end).valueOf();
    return !(busyEnd <= slotStart || busyStart >= slotEnd);
  });
}

availableTimeSlots = availableTimeSlots
  .map((slot) => {
    if (
      !checkForConflicts({
        time: slot.time,
        busy: busySlotsFromReservedSlots,
        ...availabilityCheckProps,
      })
    ) {
      return slot;
    }
    return undefined;
  })

function checkForConflicts({ busy, time, eventLength }) {
  return busy.some(busyTime => {
    const slotStart = time.valueOf();
    const slotEnd = slotStart + eventLength * 60 * 1000;
    const busyStart = dayjs.utc(busyTime.start).valueOf();
    const busyEnd = dayjs.utc(busyTime.end).valueOf();
    return !(busyEnd <= slotStart || busyStart >= slotEnd);
  });
}

availableTimeSlots = availableTimeSlots
  .map((slot) => {
    if (
      !checkForConflicts({
        time: slot.time,
        busy: busySlotsFromReservedSlots,
        ...availabilityCheckProps,
      })
    ) {
      return slot;
    }
    return undefined;
  })

function checkForConflicts({ busy, time, eventLength }) {
  return busy.some(busyTime => {
    const slotStart = time.valueOf();
    const slotEnd = slotStart + eventLength * 60 * 1000;
    const busyStart = dayjs.utc(busyTime.start).valueOf();
    const busyEnd = dayjs.utc(busyTime.end).valueOf();
    return !(busyEnd <= slotStart || busyStart >= slotEnd);
  });
}

availableTimeSlots = availableTimeSlots
  .map((slot) => {
    if (
      !checkForConflicts({
        time: slot.time,
        busy: busySlotsFromReservedSlots,
        ...availabilityCheckProps,
      })
    ) {
      return slot;
    }
    return undefined;
  })

Implémentation optimisée : O(n log n) avec tri et sortie anticipée

function checkForConflicts({ sortedBusyTimes, time, eventLength }) {
  const slotStart = time.valueOf();
  const slotEnd = slotStart + eventLength * 60 * 1000;

  for (const busyTime of sortedBusyTimes) {
    if (busyTime.start >= slotEnd) {
      break;
    }
    if (busyTime.end <= slotStart) {
      continue;
    }
    return true;
  }
  return false;
}

function checkForConflicts({ sortedBusyTimes, time, eventLength }) {
  const slotStart = time.valueOf();
  const slotEnd = slotStart + eventLength * 60 * 1000;

  for (const busyTime of sortedBusyTimes) {
    if (busyTime.start >= slotEnd) {
      break;
    }
    if (busyTime.end <= slotStart) {
      continue;
    }
    return true;
  }
  return false;
}

function checkForConflicts({ sortedBusyTimes, time, eventLength }) {
  const slotStart = time.valueOf();
  const slotEnd = slotStart + eventLength * 60 * 1000;

  for (const busyTime of sortedBusyTimes) {
    if (busyTime.start >= slotEnd) {
      break;
    }
    if (busyTime.end <= slotStart) {
      continue;
    }
    return true;
  }
  return false;
}

Ce qui a changé :
Nous avons trié les temps occupés par leurs heures de début, ce qui nous a permis de passer les périodes sans chevauchement et de sortir tôt lorsque aucun conflit n'était possible. Le résultat a été une réduction spectaculaire du nombre de comparaisons inutiles.

Impact :
La complexité a chuté de O(créneaux disponibles × périodes occupées) à O(n log n), et la plupart des vérifications ont été entièrement ignorées dans les cas typiques.

Étude de cas 2 : Intersection de plages de dates utilisant la technique des deux pointeurs

Le problème initial

La fonction intersect utilisait auparavant des boucles imbriquées pour trouver des chevauchements dans les disponibilités de plusieurs utilisateurs.

Implémentation originale : Mapping imbriqué O(n²)

commonAvailability.forEach(commonRange => {
  userRanges.forEach(userRange => {
    const intersection = getIntersection(commonRange, userRange);
    if (intersection !== null) {
      intersectedRanges.push(intersection);
    }
  });
});

commonAvailability.forEach(commonRange => {
  userRanges.forEach(userRange => {
    const intersection = getIntersection(commonRange, userRange);
    if (intersection !== null) {
      intersectedRanges.push(intersection);
    }
  });
});

commonAvailability.forEach(commonRange => {
  userRanges.forEach(userRange => {
    const intersection = getIntersection(commonRange, userRange);
    if (intersection !== null) {
      intersectedRanges.push(intersection);
    }
  });
});

Implémentation optimisée : O(n log n) avec parcours à deux pointeurs

const sortedRanges = ranges.map(userRanges =>
  userRanges
    .map(r => ({
      ...r,
      startValue: r.start.valueOf(),
      endValue: r.end.valueOf()
    }))
    .sort((a, b) => a.startValue - b.startValue)
);

let commonIndex = 0;
let userIndex = 0;

while (commonIndex < commonAvailability.length && userIndex < userRanges.length) {
  const commonRange = commonAvailability[commonIndex];
  const userRange = userRanges[userIndex];

  const intersectStartValue = Math.max(commonRange.startValue, userRange.startValue);
  const intersectEndValue = Math.min(commonRange.endValue, userRange.endValue);

  if (intersectStartValue < intersectEndValue) {
    intersectedRanges.push(createIntersection(commonRange, userRange));
  }

  if (commonRange.endValue <= userRange.endValue) {
    commonIndex++;
  } else {
    userIndex++;
  }
}

const sortedRanges = ranges.map(userRanges =>
  userRanges
    .map(r => ({
      ...r,
      startValue: r.start.valueOf(),
      endValue: r.end.valueOf()
    }))
    .sort((a, b) => a.startValue - b.startValue)
);

let commonIndex = 0;
let userIndex = 0;

while (commonIndex < commonAvailability.length && userIndex < userRanges.length) {
  const commonRange = commonAvailability[commonIndex];
  const userRange = userRanges[userIndex];

  const intersectStartValue = Math.max(commonRange.startValue, userRange.startValue);
  const intersectEndValue = Math.min(commonRange.endValue, userRange.endValue);

  if (intersectStartValue < intersectEndValue) {
    intersectedRanges.push(createIntersection(commonRange, userRange));
  }

  if (commonRange.endValue <= userRange.endValue) {
    commonIndex++;
  } else {
    userIndex++;
  }
}

const sortedRanges = ranges.map(userRanges =>
  userRanges
    .map(r => ({
      ...r,
      startValue: r.start.valueOf(),
      endValue: r.end.valueOf()
    }))
    .sort((a, b) => a.startValue - b.startValue)
);

let commonIndex = 0;
let userIndex = 0;

while (commonIndex < commonAvailability.length && userIndex < userRanges.length) {
  const commonRange = commonAvailability[commonIndex];
  const userRange = userRanges[userIndex];

  const intersectStartValue = Math.max(commonRange.startValue, userRange.startValue);
  const intersectEndValue = Math.min(commonRange.endValue, userRange.endValue);

  if (intersectStartValue < intersectEndValue) {
    intersectedRanges.push(createIntersection(commonRange, userRange));
  }

  if (commonRange.endValue <= userRange.endValue) {
    commonIndex++;
  } else {
    userIndex++;
  }
}

Ce qui a changé :
En triant et en utilisant deux pointeurs pour parcourir les plages, nous avons éliminé le besoin d'itération imbriquée. Cela a réduit la complexité de quadratique à presque linéaire pour la plupart des entrées pratiques.

Étude de cas 3 : Arbre d'intervalles pour le filtrage de plages redondantes

Le problème initial

La fonction filterRedundantDateRanges vérifiait chaque plage par rapport à chaque autre pour voir si l'une contenait l'autre. Pour des plannings importants, cela devenait douloureusement lent.

Implémentation originale : Vérification de contenance O(n²)

return dateRanges.filter((range, index) => {
  return !dateRanges.some((otherRange, otherIndex) => {
    if (index === otherIndex) return false;
    return isCompletelyContained(range, otherRange);
  });
});

return dateRanges.filter((range, index) => {
  return !dateRanges.some((otherRange, otherIndex) => {
    if (index === otherIndex) return false;
    return isCompletelyContained(range, otherRange);
  });
});

return dateRanges.filter((range, index) => {
  return !dateRanges.some((otherRange, otherIndex) => {
    if (index === otherIndex) return false;
    return isCompletelyContained(range, otherRange);
  });
});

Implémentation optimisée : O(n log n) avec un arbre d'intervalles

export function filterRedundantDateRanges(dateRanges) {
  const sortedRanges = [...dateRanges].sort((a, b) => a.start.valueOf() - b.start.valueOf());
  const intervalNodes = createIntervalNodes(
    sortedRanges,
    (range) => range.start.valueOf(),
    (range) => range.end.valueOf()
  );
  const intervalTree = new IntervalTree(intervalNodes);
  const searchAlgorithm = new ContainmentSearchAlgorithm(intervalTree);

  return sortedRanges.filter((range, index) => {
    const containingIntervals = searchAlgorithm.findContainingIntervals(
      range.start.valueOf(),
      range.end.valueOf(),
      index
    );
    return containingIntervals.length === 0;
  });
}

export function filterRedundantDateRanges(dateRanges) {
  const sortedRanges = [...dateRanges].sort((a, b) => a.start.valueOf() - b.start.valueOf());
  const intervalNodes = createIntervalNodes(
    sortedRanges,
    (range) => range.start.valueOf(),
    (range) => range.end.valueOf()
  );
  const intervalTree = new IntervalTree(intervalNodes);
  const searchAlgorithm = new ContainmentSearchAlgorithm(intervalTree);

  return sortedRanges.filter((range, index) => {
    const containingIntervals = searchAlgorithm.findContainingIntervals(
      range.start.valueOf(),
      range.end.valueOf(),
      index
    );
    return containingIntervals.length === 0;
  });
}

export function filterRedundantDateRanges(dateRanges) {
  const sortedRanges = [...dateRanges].sort((a, b) => a.start.valueOf() - b.start.valueOf());
  const intervalNodes = createIntervalNodes(
    sortedRanges,
    (range) => range.start.valueOf(),
    (range) => range.end.valueOf()
  );
  const intervalTree = new IntervalTree(intervalNodes);
  const searchAlgorithm = new ContainmentSearchAlgorithm(intervalTree);

  return sortedRanges.filter((range, index) => {
    const containingIntervals = searchAlgorithm.findContainingIntervals(
      range.start.valueOf(),
      range.end.valueOf(),
      index
    );
    return containingIntervals.length === 0;
  });
}

Ce qui a changé :
Au lieu de la comparaison forcée, nous avons utilisé une structure d'arbre d'intervalles pour permettre des requêtes de contenance O(log n) rapides. C'est une approche classique en géométrie computationnelle qui fonctionne à merveille pour les applications de planification.

Résultats de performance : Avant et après

Nos benchmarks ont montré des améliorations significatives :

• Vérification des conflits de créneaux : Réduit de O(n²) à O(n log n), rendant 100 créneaux et 50 périodes occupées environ dix fois plus rapides.

• Intersection de plages de dates : Passé de O(n²) à O(n log n), permettant le traitement de centaines de plages de dates en millisecondes.

• Filtrage de plages redondantes : Réduit de O(n²) à O(n log n), avec jusqu'à cinquante fois plus de rapidité pour des milliers de plages de dates.

• Intersection de plages générales : À travers de nombreux schémas, nous avons constaté des améliorations de vingt-cinq fois ou plus.

Techniques simples pour détecter les algorithmes O(n²)

Reconnaître les schémas problématiques

Surveillez pour :

• Itérations de tableaux imbriqués, en particulier .map, .forEach, .filter à l'intérieur d'un autre.

• Méthodes de tableau comme .some, .find, ou .filter à l'intérieur de boucles ou dans les rappels de tableau.

• Filtres chaînés ou mapping imbriqué sur de grandes listes.

Tester explicitement l'évolutivité

Écrivez des tests de performance qui exécutent votre fonction sur des données de taille croissante et enregistrez les temps d'exécution. Si le temps croît de façon quadratique avec la taille des données, vous avez un problème O(n²).

Automatiser l'analyse statique

Ajoutez des règles de lint ou une analyse statique qui :

• Signale les fonctions avec des boucles imbriquées ou des méthodes de tableau imbriquées.

• Identifie la récursivité sans mémoïsation.

• Détecte les fonctions avec plusieurs appels imbriqués .some, .find, ou .filter.

Stratégies éprouvées pour remplacer le code O(n²)

• Utiliser la recherche binaire pour les recherches dans les tableaux triés.

• Utiliser des techniques à deux pointeurs pour fusionner ou intercepter des séquences triées.

• Utiliser des structures de données basées sur les arbres pour les requêtes d'intervalles ou les données hiérarchiques.

Automatisation des vérifications de performance

Ajoutez des benchmarks de performance à votre pipeline CI qui exécutent les algorithmes critiques sur des données réalistes. Comparez les temps d'exécution à chaque pull request et bloquez les fusions qui entraînent des régressions. Ajoutez des règles de lint personnalisées pour empêcher que des modèles O(n²) évidents n'atteignent jamais la production. Mettez en œuvre une surveillance du temps d'exécution pour les chemins critiques afin de détecter les nouvelles régressions avant que les utilisateurs ne les remarquent.

Points clés à retenir

• La prévention est toujours meilleure que la guérison. Les vérifications automatisées détecteront les algorithmes O(n²) avant qu'ils ne causent des problèmes.

• Toujours profiler avant d'optimiser. Utilisez des tests pour trouver les véritables goulets d'étranglement.

• Choisissez les bonnes structures de données pour vos besoins. Les tableaux triés, les approches à deux pointeurs, et les arbres sont inestimables.

• Testez avec des données réalistes et à grande échelle. Les petits tests peuvent cacher de gros problèmes.

• Surveillez en production. Les alertes automatisées peuvent détecter les régressions tôt.

Conclusion

Les optimisations que nous avons réalisées chez Cal.com montrent que des gains de performance significatifs sont possibles en appliquant des techniques algorithmiques éprouvées. Combinez la révision de code, des structures de données intelligentes, et une surveillance automatisée pour garder votre application rapide à mesure qu'elle évolue.

La performance doit être intégrée à chaque étape du développement, des revues de code qui signalent des modèles suspects aux pipelines CI qui exécutent des tests de scalabilité et une surveillance du temps d'exécution qui détecte les régressions.

L'algorithme rapide d'aujourd'hui peut facilement devenir le goulet d'étranglement de demain à mesure que vos données croissent. Restez vigilant, testez à grande échelle, et soyez toujours prêt à optimiser.