Avatar billede dsj Nybegynder
22. december 2003 - 16:24 Der er 15 kommentarer og
2 løsninger

Hvorfor er denne operation så dyr

Jeg har en server med et antal arbejder-tråde. Arbejderne aktiveres ved at lægge noget i deres "handoff-box" (en QueueArray-instans med 1 plads). Så længe der ikke er noget at lave, står arbejderen altså blokkeret i QueueArray.remove(), der er en synkroniseret metode, som anvender wait(), så længe køen er tom. QueueArray ses nedenfor.

I et server-scenarie står remove() der kalder waitWhileEmpty(), altså wait(), for over 60% af CPU-forbruget, altså over 60% af den tid, den aktuelle tråd faktisk er på CPU'en, hvordan i al verden kan det være !?

package com.shockwaved.octane.shared.util;

public class QueueArray {
  private Object[] queue;
  private int capacity;
  private int size;
  private int head;
  private int tail;

  public QueueArray(int cap) {
    capacity = (cap > 0) ? cap : 1;
    queue = new Object[capacity];
    head = 0;
    tail = 0;
    size = 0;
  }

  public int capacity() { return capacity; }

  public synchronized int size() { return size; }

  public synchronized boolean isEmpty() { return (size == 0); }

  public synchronized boolean isFull() { return (size == capacity); }

  public synchronized void add(Object obj) throws InterruptedException {
    waitWhileFull();
    queue[head] = obj;
    head = (head + 1) % capacity;
    size++;
    notifyAll();
  }

  public synchronized Object remove() throws InterruptedException {
    waitWhileEmpty();
    Object obj = queue[tail];
    queue[tail] = null;
    tail = (tail + 1) % capacity;
    size--;
    notifyAll();
    return obj;
  }

  private synchronized void waitWhileEmpty() throws InterruptedException {
    while (isEmpty()) { wait(); }
  }

  private synchronized void waitWhileFull() throws InterruptedException {
    while (isFull()) { wait(); }
  }
}
Avatar billede jakoba Nybegynder
22. december 2003 - 17:43 #1
Jeg fatter ikke at det overhovedet virker.

remove er synkroniseret, så når du venter *indeni* remove er din instans af QueArray konstant låst, så det skulle slet ikke være muligt at kalde add metoden.

men det er det åbenbart. mon ikke arne_v kan forklare hvorfor :-))
Avatar billede arne_v Ekspert
22. december 2003 - 17:49 #2
Em anden synchronized method kan godt komme til når den første er gået i wait.
Avatar billede dsj Nybegynder
22. december 2003 - 17:50 #3
wait() frigiver modsat sleep() alle låse.
Avatar billede dsj Nybegynder
22. december 2003 - 17:52 #4
Jeg vil nu hellere have arne til at forklare hvordan #¤&%#¤% det kan være at mere end halvdelen af CPU-tiden går i waitWhileEmpty() ... :)
Avatar billede arne_v Ekspert
22. december 2003 - 17:54 #5
Jeg kigger på det.

For det lyder voldsomt med 60%.
Avatar billede arne_v Ekspert
22. december 2003 - 18:24 #6
Hvor mange add & remove dækker de 60% over ?

Jeg få 1 million add+remove på 26 s ved 99% CPU usage på en 2 GHz CPU.

(do nothing eksempel)
Avatar billede dsj Nybegynder
22. december 2003 - 18:25 #7
Det synes jeg så bestemt også. Baggrunden for tallet er en test jeg har kørt sammen med Borlands Profiler fra OptimizeIt-suiten. Testen gik ud på at 20 klienter hver, hvert 3. sekund har sendt en besked til serveren, som så er returneret til alle 20. CPU-målingen varede i ca. 5 minutter og blev gennemført et stykke tid efter at testen faktisk var startet således, at JVM har nået at kompilere det nødvendige til nativ kode.

Serveren kørte med 5 worker-tråde og ved modtagelse af beskeder fra klienterne er der foretaget en del beregninger, gået gennem kritiske regioner mv., så der er ikke tale om blot echo.

Belastningen har altså i snit været 6,67 modtagede beskeder i sekundet og 133,33 sendte.
Avatar billede dsj Nybegynder
22. december 2003 - 18:26 #8
Der er tale om en 1,4 GHz AMD, og da testen har kørt fra JBuilder inkl profileren, er der gået en del ressourcer hertil...
Avatar billede arne_v Ekspert
22. december 2003 - 18:29 #9
Mystisk.

1 million / 26 s = 38000 per sekund
Avatar billede arne_v Ekspert
22. december 2003 - 18:39 #10
Jeg har selv noget queue kode liggende som giver 184000 per sekund.

Hvilket jo er er tæt på ovenstående (throughput fordobles bar eved
at øge capacity fra 1 til 10 - og min kode har ikke nogen
restriktion).
Avatar billede arne_v Ekspert
22. december 2003 - 18:40 #11
Kunne du prøve at køre mit test program på din box og se hvad det giver:

public class Test {
    public static void main(String[] args) throws Exception {
        QueueArray qa = new QueueArray(1);
        T1[] t1 = new T1[100];
        T2[] t2 = new T2[100];
        for(int t = 0; t < 100; t++) {
            t1[t] = new T1(qa);       
            t2[t] = new T2(qa);       
        }
        long start = System.currentTimeMillis();
        for(int t = 0; t < 100; t++) {
            t1[t].start();
            t2[t].start();
        }
        for(int t = 0; t < 100; t++) {
            t1[t].join();
            t2[t].join();
        }
        long end = System.currentTimeMillis();
        System.out.println("done in " + (end - start));
    }
}

class T1 extends Thread {
    private QueueArray qa;
    T1(QueueArray qa) {
        this.qa = qa;
    }
    public void run() {
        try {
            for(int i = 0; i < 10000; i++) {
                qa.add(new Integer(123));
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

class T2 extends Thread {
    private QueueArray qa;
    T2(QueueArray qa) {
        this.qa = qa;
    }
    public void run() {
        try {
            for(int i = 0; i < 10000; i++) {
                Integer v = (Integer)qa.remove();
                if(v.intValue() != 123) {
                    System.err.println("v=" + v);
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}
Avatar billede dsj Nybegynder
22. december 2003 - 18:52 #12
Min maskine er 36,7 sekunder om din test...

Jeg prøvede i øvrigt at flytte indholdet af waitWhileEmpty() ind i remove(), så nogen metode-kald kunne undgås:

  public synchronized Object remove() throws InterruptedException {
    while (size == 0) { wait(); }
    Object obj = queue[tail];
    queue[tail] = null;
    tail = (tail + 1) % capacity;
    size--;
    notifyAll();
    return obj;
  }

En CPU-profilertest gav følgende output:

Description of CPU usage for thread Worker: 2
  100.0% - 8255 ms - Worker$1.run()
      100.0% - 8255 ms - Worker.access$000()
        100.0% - 8255 ms - Worker.start()
            62.83% - 5187 ms - QueueArray.remove()
            19.3% - 1594 ms - Worker.handleWrite()
            15.78% - 1303 ms - Worker.handleSelectionKey()
            1.7% - 141 ms - BalancedWorkerPool.releaseWorker()
Avatar billede arne_v Ekspert
22. december 2003 - 19:31 #13
1 million / 36.7 s = 27000 per sekund ved 99% CPU load

Så har jeg svært ved at forstå hvordan 7 per sekund kan bruge 60%

Der må være en faktor X
Avatar billede dsj Nybegynder
23. december 2003 - 00:37 #14
Ok, jeg har fundet ud af det. Profileren måler program eksekveringstid, ikke CPU-tid, hvorfor tiden brugt i waitWhileEmpty() angiver hvor lang tid tråden har sovet. Tak for hjælpen og besværet.
Avatar billede dsj Nybegynder
23. december 2003 - 00:37 #15
I må godt smide et svar, så i lige får lidt for besværet...
Avatar billede dsj Nybegynder
23. december 2003 - 00:40 #16
I øvrigt udførte jeg en lille test, hvor serveren absolut intet lavede så længe CPU-belastningen måltes. Resultatet blev, at alle workere havde brugt 100% tid i waitWhileEmpty()
Avatar billede arne_v Ekspert
23. december 2003 - 08:19 #17
Når enden er god
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester