Trovare e risolvere i colli di bottiglia delle prestazioni O(n²): Lezioni dalle ottimizzazioni algoritmiche di Cal.com

Introduzione

I colli di bottiglia delle prestazioni nei sistemi di pianificazione possono fare la differenza tra un'esperienza utente reattiva e utenti che abbandonano la tua piattaforma per frustrazione. In Cal.com, abbiamo recentemente scoperto e ottimizzato diversi algoritmi critici O(n²) che stavano causando rallentamenti con l'aumento della nostra base utenti e dei volumi di dati.

In questo articolo, condividerò quattro ottimizzazioni algoritmiche reali dal codice di Cal.com. Imparerai come abbiamo rilevato la complessità O(n²), quali strategie di ottimizzazione hanno funzionato meglio e come abbiamo implementato controlli automatizzati per prevenire regressioni future.

Il problema: come il codice innocente diventa O(n²)

Man mano che le piattaforme di pianificazione crescono, è sorprendentemente facile per cicli nidificati apparentemente innocenti diventare letali per le prestazioni. Considera questo esempio reale dal nostro codice:

// 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));
});

Per 100 slot e 50 periodi di occupazione, sono 5.000 controlli di sovrapposizione. Su scale più ampie—500 slot e 200 periodi di occupazione—esplode a 100.000 operazioni. È un aumento del carico computazionale di venti volte per un aumento dei dati di sole cinque volte.

Studio di caso 1: Ottimizzazione del controllo dei conflitti di slot

Il problema originale

La funzione checkForConflicts utilizzava l'iterazione nidificata per verificare se gli slot di prenotazione erano in conflitto con i periodi di occupazione. Questo è diventato rapidamente un problema di prestazioni con grandi pianificazioni.

Implementazione originale: cicli nidificati 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;
  })

Implementazione ottimizzata: O(n log n) con ordinamento e uscita anticipata

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;
}

Cosa è cambiato:
Abbiamo ordinato i tempi di occupazione per gli orari di inizio, il che ci ha permesso di saltare periodi non sovrapposti e uscire anticipatamente quando non era possibile alcun conflitto. Il risultato è stato una drastica diminuzione del numero di confronti non necessari.

Impatto:
La complessità è scesa da O(slot disponibili × periodi di occupazione) a O(n log n), e la maggior parte dei controlli sono stati completamente evitati nei casi tipici.

Studio di caso 2: Intersezione dell'intervallo di date utilizzando la tecnica a due puntatori

Il problema originale

La funzione intersect utilizzava precedentemente cicli nidificati per trovare sovrapposizioni tra le disponibilità di più utenti.

Implementazione originale: mappatura nidificata 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);
    }
  });
});

Implementazione ottimizzata: O(n log n) con attraversamento a due puntatori

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++;
  }
}

Cosa è cambiato:
Ordinando e utilizzando due puntatori per attraversare gli intervalli, abbiamo eliminato la necessità di un'iterazione nidificata. Questo ha ridotto la complessità da quadratica a quasi lineare per la maggior parte degli input pratici.

Studio di caso 3: Albero di intervalli per il filtraggio di intervalli ridondanti

Il problema originale

La funzione filterRedundantDateRanges controllava ogni intervallo rispetto a ogni altro per vedere se uno conteneva l'altro. Per grandi pianificazioni, questo diventava dolorosamente lento.

Implementazione originale: controllo del contenimento 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);
  });
});

Implementazione ottimizzata: O(n log n) con un albero di intervalli

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;
  });
}

Cosa è cambiato:
Invece di un confronto a forza bruta, abbiamo usato una struttura ad albero di intervalli per consentire query di contenimento rapide O(log n). Questo è un approccio classico nella geometria computazionale che funziona meravigliosamente per le applicazioni di pianificazione.

Risultati delle prestazioni: Prima e dopo

I nostri benchmark hanno mostrato miglioramenti significativi:

• Controllo dei conflitti di slot: Ridotto da O(n²) a O(n log n), rendendo più veloci di circa dieci volte 100 slot e 50 periodi di occupazione.

• Intersezione dell'intervallo di date: Passato da O(n²) a O(n log n), permettendo di elaborare centinaia di intervalli di date in millisecondi.

• Filtraggio di intervalli ridondanti: Ridotto da O(n²) a O(n log n), con un incremento di velocità fino a cinquanta volte per migliaia di intervalli di date.

• Intersezione dell'intervallo generale: In molti modelli, abbiamo visto miglioramenti di venticinque volte o più.

Tecniche facili per rilevare gli algoritmi O(n²)

Riconoscere i modelli di problema

Presta attenzione a:

• Iterazioni di array nidificate, specialmente .map, .forEach, .filter dentro un'altra.

• Metodi di array come .some, .find o .filter all'interno di cicli o callback di array.

• Filtri concatenati o mappature nidificate su liste grandi.

Testare esplicitamente la scalabilità

Scrivi test di prestazioni che eseguano la tua funzione su dati di dimensioni crescenti e registrano i tempi di esecuzione. Se il tempo cresce in modo quadratico rispetto alla dimensione dei dati, hai un problema O(n²).

Automatizzare l'analisi statica

Aggiungi regole lint o analisi statica che:

• Evidenziano funzioni con cicli nidificati o metodi di array nidificati.

• Identificano la ricorsione senza memoizzazione.

• Rilevano funzioni con più chiamate .some, .find o .filter nidificate.

Strategie comprovate per sostituire il codice O(n²)

• Usa la ricerca binaria per le ricerche in array ordinati.

• Utilizza tecniche a due puntatori per unire o intersecare sequenze ordinate.

• Usa strutture dati basate su alberi per query sugli intervalli o dati gerarchici.

Automatizzare i controlli delle prestazioni

Aggiungi benchmark delle prestazioni al tuo pipeline CI che eseguono algoritmi critici su dati realistici. Confronta i tempi di esecuzione su ogni pull request e blocca le fusioni che causano regressioni. Aggiungi regole lint personalizzate per prevenire l'arrivo in produzione di pattern O(n²) evidenti. Implementa il monitoraggio del runtime per percorsi critici per catturare nuove regressioni prima che gli utenti se ne accorgano.

Punti chiave

• La prevenzione è sempre meglio che curare. Controlli automatizzati rileveranno gli algoritmi O(n²) prima che causino problemi.

• Sempre profilare prima di ottimizzare. Utilizza i test per trovare i veri colli di bottiglia.

• Scegli le strutture dati giuste per le tue esigenze. Array ordinati, approcci a due puntatori e alberi sono preziosi.

• Testa con dati realistici e su larga scala. I piccoli test possono nascondere grandi problemi.

• Monitora in produzione. Gli avvisi automatizzati possono rilevare regressioni in anticipo.

Conclusione

Le ottimizzazioni che abbiamo fatto in Cal.com dimostrano che sono possibili notevoli miglioramenti delle prestazioni applicando tecniche algoritmiche comprovate. Combina il controllo del codice, strutture dati intelligenti e monitoraggio automatizzato per mantenere la tua applicazione veloce man mano che cresce.

Le prestazioni dovrebbero essere integrate in ogni fase dello sviluppo, dai codici di revisione che evidenziano pattern sospetti ai pipeline CI che eseguono test di scalabilità e monitoraggio del runtime che rilevano regressioni.

L'algoritmo veloce di oggi può facilmente diventare il collo di bottiglia di domani con la crescita dei tuoi dati. Rimani vigile, testa su scala e sii sempre pronto a ottimizzare.