Die Verwendung von Warteschlangen- und First-In-First-Out-Algorithmen scheint eine Standardmethode für die Verarbeitung von Anforderungen an Server/Datenbanken/Dienste zu sein. Aber könnten andere Datenstrukturen und Algorithmen für den Umgang mit großen Mengen von Anfragen verwendet werden?Verwenden anderer Datenstrukturen und Algorithmen als Warteschlangen und FIFOs für die Verarbeitung und Priorisierung von Anforderungen
Es gibt einen Artikel unter http://queue.acm.org/detail.cfm?id=2991130 "Skalierungssynchronisation in Multicore-Programmen", der in das Detail der Reduzierung der Schließungskosten eingeht, wenn mehrere Kerne versuchen, die gleiche FIFO-Warteschlange zu aktualisieren.
Wenn unterschiedliche Benutzer oder unterschiedliche Anforderungen unterschiedliche Prioritäten haben, wird eine FIFO-Warteschlange nicht ausgeführt, und Sie benötigen etwas, das die Priorität berücksichtigt. Ich habe oft gesehene Karten dafür verwendet, wie TreeMap und std :: map oder std :: multimap. Es ist nicht der Anwendungsfall, für den diese entwickelt wurden, aber die Leute wissen, wie man sie verwendet, und sie sind in der Regel hoch optimiert, so dass sie schneller sein können, als die meisten Leute versuchen, eine spezialisiertere Datenstruktur zu implementieren.
"Ich habe oft geordnete Karten dafür verwendet" [Autsch] (https://youtu.be/fHNmRkzxHWs?t=2708) "und sie sind in der Regel hoch optimiert" - vielleicht sind sie optimiert, aber ** nicht ** für die Leistung. –
In der Single-Prozessor-Single-Core-Fall sah ich einige Software, die std :: map als Priorität-Warteschlange verwendet, mit einer erheblichen Menge an Zeit in std :: map verbrachte. Ich habe std: map als eine Prioritätswarteschlange verglichen mit meiner eigenen sehr einfachen Implementierung einer spezialisierteren Alternative - es könnte ein Haufen gewesen sein, aber ich vergesse die Details jetzt. Ich habe keinen Leistungszuwachs gesehen, der die Änderung des ursprünglichen Programms gerechtfertigt hätte. – mcdowella
"Ich habe std: map als eine Prioritätswarteschlange verglichen mit meiner eigenen sehr einfachen Implementierung einer spezialisierteren Alternative - es könnte ein Haufen gewesen sein", Heh, Benchmarking einer Baumstruktur gegen eine andere Baumstruktur? Ich habe mir selbst versprochen, dass ich eine "Einfügesortierung" in einem Vektor gegen den von std :: map implementierten RB-Baum benchmarken werde. Ich könnte mit einem In-Memory-B-Tree-Typ gehen - die CPU-Caches reagieren auf normalen RAM genauso wie der RAM auf Festplattenzugriffe reagiert, also warum nicht? –