O (log n) per la gestione della memoria è considerato lento?

La performance "ideale" di un algoritmo nella mente delle persone dipende da quale sia l'opzione migliore là fuori. Se è possibile eseguire un'operazione di "ricerca" su una struttura di dati in tempo O (n log N), è abbastanza veloce? Forse lo è. Tuttavia, per molte strutture puoi fare una ricerca in O (n), o anche O (log n), così la gente chiamerà il tuo O (n log n) "lento". Questo non perché è in realtà lento, ma perché ci sono algoritmi più veloci che soddisfano le loro esigenze.

In generale, le persone hanno trovato algoritmi che girano più velocemente di O (log n) che soddisfano le loro aspettative sulla gestione della memoria. Pertanto, qualsiasi algoritmo O (log n) verrà contrassegnato come "troppo lento" dal popoloso generale, a meno che non offra alcune funzionalità valide per compensare questo cambio di velocità. Non venderai molte auto sportive con motori 50HP in un paese in cui gli sportcar hanno tutti 250 + HP, a meno che tu non possa mostrare un valore unico di questa vettura sportiva 50HP. Forse è più economico o biodegradabile.

La maggior parte degli sviluppatori che usano questi algoritmi di gestione della memoria non vogliono pensare al costo dell'API sottostante. Se devono anche considerare le prestazioni di runtime asintotiche della loro gestione della memoria, allora è troppo lento per loro. Lo rifiuteranno.

Tutto ciò significa che le vere librerie di gestione della memoria tendono a modellare le prestazioni in modo più sfumato rispetto alla semplice notazione Big-Oh. Big-Oh è bello, ma per il tipo di performance a cui sono interessati, non è abbastanza buono. I gestori della memoria devono preoccuparsi delle costanti di tempo effettive che governano la velocità di esecuzione, che Big-Oh semplicemente ignora. Le loro analisi runtime includono cose come errate previsioni delle branche e jitter e letture / scritture non casuali per ottenere un po 'di prestazioni in più.

Quindi alla fine, se viene data la possibilità di scegliere tra un algoritmo O (log n) e un algortihm sintonizzato con bordo sanguinante che richiede 3 cicli per allocare oggetti più piccoli di 64 byte e 20-40 cicli per oggetti più grandi, quale hai intenzione di scegliere?

"Slow" dipende dall'applicazione. Per alcune applicazioni in tempo reale (controllo dei macchinari ad alta velocità, DSP, ecc.), Qualsiasi latenza non limitata potrebbe essere troppo lenta, causando forse persino una modalità di errore catastrofico. Per queste applicazioni, il codice O (1) è più facile da verificare come sicuro. O (logN) è sicuro solo se N è strettamente limitato e all'interno dei requisiti, e max (N) potrebbe essere difficile da determinare, verificare o testare.

Ad esempio, l'obiettivo C include la gestione della memoria di conteggio dei riferimenti, eppure Apple raccomanda ancora contro l'uso di metodi che possono allocare memoria all'interno di contesti audio in tempo reale iOS / macOS. Non vuoi un sintetizzatore musicale dal vivo per far risaltare gli oratori di sale da concerto.

I am talking about single thread general purpose memory allocation/deallocation from a global 'heap' as e.g. every C programmer knows in the form of malloc()/free().

Penso che la risposta sarebbe abbastanza simile a ciò che viene utilizzato all'interno di un sistema operativo, ad es. Kernel Linux. Il problema qui è, è lento? Certo che no, O (log n) è veloce. È sempre veloce? Risulta che alcuni algoritmi sono veloci per la ricerca ma non così veloci per l'inserimento / la cancellazione, mentre altri sono più veloci nell'inserimento / eliminazione ma non così veloci per la ricerca.

Ad esempio, sia l'albero AVL che l'albero rosso-nero sono O (log n). Per citare la documentazione del kernel :

Red-black trees are similar to AVL trees, but provide faster real-time bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time.

Nel caso in cui venga utilizzato un albero rosso-nero, ci sono quantità significative di operazioni di inserimento / cancellazione e questo potrebbe non essere il caso per tutte le applicazioni.

Questo dovrebbe dare una buona idea di come dovrebbe funzionare un algoritmo. Il pizzico di sale è, dipende dall'applicazione e il modo per scoprirlo è la profilazione.