Java Wie am einfachsten und schnellsten Long-Ringpuffer erstellen?

[pudel-2]

Moin, ich würde gerne wissen, ob dies die einfachste und zugleich schnellste Art ist, um einen Long-Ringpuffer in Java zu erstellen...

Es soll gezählt werden, ob es mehr als X (fest) Zugriffe innerhalb der letzten 2 Minuten gab... für ca. 20000 Elemente (deshalb sollte dafür nicht all zu viel Zeit verbraten werden):

  private static boolean hitAndCheck(long[] seenAt) {
    final int hitLimit = 20;
    if (seenAt == null || seenAt.length < hitLimit) {
      return false;
    }
    long currentTime = System.currentTimeMillis();
    long threshold = currentTime - (1000 * 120);
    int size = 1;
    for (int i = 0; i < seenAt.length; i++) {
      if (seenAt[i] < threshold) {
        seenAt[i] = 0;
      } else if (seenAt[i] != 0) {
        size++;
      }
    }
    Arrays.sort(seenAt);
    seenAt[0] = currentTime;
    if (size >= hitLimit) {
      logger.warn("Hit limit exceeded: {} at {}", hitLimit, currentTime);
      return true;
    }
    return false;
  }

 

[TorenAltair]

Sofern ich mich richtig erinnere ist float bei heutigen CPUs deutlich schneller als int/long.

 

[pudel-2]

ist float bei heutigen CPUs deutlich schneller als int/long

Völliger Quatsch.

Ergänzung (Gestern um 13:59)

Nachdem das Java-Forum geschlossen wurde

Das ist wieder erreichbar... (jedenfalls war es das vorhin noch.) Ob Konrad gestorben ist, weiß ich aber nicht.

 

[Tsu]

Benchmarke mal deine Lösungsidee gegen einen etwas ungenaueren Zähler oder zwei pro Minute (der zweite hätte Versatz).

Ein Ringpuffer ist die naheliegendste Lösung, eine Buchlösung.

Die von mir angeregte klingt erstmal naiv, führt aber später zu einem deutlich besseren und verteilbaren System.

 

[madmax2010]

Völliger Quatsch.

ne, @TorenAltair hat recht.. X86 hat sich in den letzten 40 jahren ein bisschen weiter entwickelt.
Selbst ohne SIMD oder vektorisierung

deine reaktion auf die vorherigen lässt jedoch darauf schließen dass man sagen kann, Hi Cyborg-Beta

 

[pudel-2]

@madmax2010 Wie willst du den +1 auf float machen?

 

[madmax2010]

+1.0f

 

[Tsu]

Lass dich von so Kleinkram wie float vs int (mutmaßlich später AtomicInteger, LongAccumulator, …) erstmal nicht ablenken.

Mit System.currentTimeMillis hast du ja schon einen (cachebaren, VDSO) Zugriff mehr als nötig. ;-)

 

[pudel-2]

@madmax2010 In der Methode rechne ich doch gar nicht viel. Einmal - und ein < Vergleich innerhalb einer Schleife. Ich denke, es ginge mehr Zeit dabei verloren (und auch Genauigkeit...), den Zeitstempel erst in ein float zu pressen.

 

[Wo bin ich hier]

Mach den sort auf "long[] seenAt" einmalig außerhalb (oder ist das eventuell bereits immer sortiert?!), dann brauchst du nichts mehr loopen/sortieren.
Es reicht dann den ältesten Eintrag zu prüfen, ob dieser innerhalb deines Zeitfensters ist (wenn der 20. Eintrag innerhalb von 2 Min passiert ist, dann auch alle anderen).

Als Referenz via KI generiert:

public final class HitLimiter {

    private static final int HIT_LIMIT = 20;
    private static final long WINDOW_MS = 120_000;

    private final long[] hits = new long[HIT_LIMIT];
    private int index = 0;
    private int count = 0;

    public boolean hitAndCheck() {
        long now = System.currentTimeMillis();

        hits[index] = now;
        index = (index + 1) % HIT_LIMIT;

        if (count < HIT_LIMIT) {
            count++;
            return false;
        }

        long oldest = hits[index];

        boolean exceeded = (now - oldest) <= WINDOW_MS;

        if (exceeded) {
            logger.warn("Hit limit exceeded: {} at {}", HIT_LIMIT, now);
        }

        return exceeded;
    }
}

 

[pudel-2]

@Wo bin ich hier Es gibt 20000 solcher Arrays, nicht nur eins. Und wie soll der neuste einsortiert werden ohne sort?

 

[Wo bin ich hier]

Es gibt 20000 solcher Arrays, nicht nur eins

Sind die sortiert? Kommen die fix aus einer Datenbank? Oder sind das Live-Zähler, z.B. Benutzeraufrufe, die du mitzählen willst? Am Besten mal den Use Case genauer erklären und Beispieldaten bereitstellen.

Und wie soll der neuste einsortiert werden ohne sort?

Siehst du im Code oben (dazu müsste man halt den Index mittracken; das ist dann eher der Use Case "Live-Zähler"). Da du von "Zugriffen" sprichst, sollte es doch darum gehen, oder nicht?

 

[KingLz]

Es gibt 20000 solcher Arrays, nicht nur eins. Und wie soll der neuste einsortiert werden ohne sort?

Na am Ende, wo das Ende aktuell liegt, wenn es ein Ringspeicher ist.
Anfang und Ende von einem Ring wandern ja permanent, sobald dieser das erste Mal voll ist.

Die Lösung von Wo bin ich hier sieht doch schon sehr gut aus.
Die Idee ist einfach du speicherst die letzten X (Hit limit) Zugriffe und deren Zeitmarke.
Sobald der Ringspeicher voll wird ist neues Ende = alter Anfang.
Wenn neues Ende Zeit - alter Anfang Zeit < Minimale Wartezeit (2Min) dann weißt du das Limit muss aktiv werden.

Aktiv sortieren solltest du niemals, das braucht nur extrem viele Resourcen. Wenn du eine Liste/Array von 0 bis Ende aufsteigend füllst ist es ja schon sortiert. Bei einem Ring musst du dir nur den aktuellen Anfang merken, da wenn die Liste/Array voll ist Platz 0 auf Platz 1 und das Ende X auf 0 rückt und so weiter.

 

[Tornhoof]

Array.Sort kann nie "performant" sein wenn du das häufig genug aufrufst und seenAt groß genug wird.
Wieso machst du nicht ein TimingWheel für alle Einträge (also nicht 20000 arrays, sondern ein Array, mit einer Granularität von einer Sekunde) und in das Datenobjekt schreibst deinen indikato, z.b. IP + counter rein.

Timing Wheels werden gerne für granulare Caches mit Expiry eingesetzt (was bei dir nicht viel Unterschiedlich ist), siehe u.A. https://pncnmnp.github.io/blogs/timing-wheels.html

 

[Zensai]

Wie oft denn noch: Egal wie vie oft du es versuchst: du hast hier Hausverbot!