tifyty

pure Java, what else ?

Miért ne legyen több, mint 9 thread lokál változónk?

Egy korábbi cikkben azt fejtegettem, hogy lassú-e a thread local, és mint vátesz, kijelentettem, hogy egy programban (egy classloader alatt) ne használjunk több, mint 9 ThreadLocal változót ha zavar minket, hogy a Thread objektum threadLocals map-jában egybeesés van, vagy, hogy a JDK átszervezi a map-et (ami relatíve lassú folyamat). Honnan jött ez a 9? Miért 9, miért nem 10, vagy 16?

Na, akkor vágjunk bele.

Először is a 9 egy olyan szám, amelyikre abban a JDK-ban, amelyiket

java -version
java version "1.7.0_07"
Java(TM) SE Runtime Environment (build 1.7.0_07-b10)
Java HotSpot(TM) 64-Bit Server VM (build 23.3-b01, mixed mode)

megnéztem garantált, hogy nem lesz ütközés (egybeesés), sem map átstrukturálás. Ezt azonban nem a szabvány garantálja, és nem a JDK API. Egyszerűen csak látszik a kódból, így előfordulhat, hogy régebbi, újabb, vagy éppen más architektúrára készített JDK-ban ez nem így van.

Azt sem lehet állítani, hogy ha egy programban több, mint kilenc ThreadLocal változópéldány van, akkor lesz ütközés, vagy map átstrukturálás. Előfordulhat, hogy nem lesz. Mint a kertmozi előadás. Ha eső lesz nem lesz. Ha nem lesz, akkor lesz.

A ThreadLocalMap a ThreadLocal osztály egy statikus belső osztálya. Mint minden rendes map, ez is tartalmaz entry-ket. Ez az entry azonban a HashMap entry-jével ellentétben nem tartalmaz next mezőt ellenben saját maga a WeakReference<ThreadLocal> leszármazottja.

Miért érdekes az, hogy nem tartalmaz next mezőt? Azért, mert ütközésnél nem azt csinálja, amit a HashMap, nem fűzi fel egy láncolt listára az elemeket, hanem elkezdi keresni a hash táblában a következő, első üres cellát. Ha minden cella betelt, és körbeért, akkor végtelen ciklusba kerül (haha!). De ez nem következik be, mert amikor 2/3-ig betelt a tábla, akkor megnöveli kétszeresére a táblaméretet. (A HashMap nézi, hogy nem nő-e túl nagyra a tábla mérete, a ThreadLocalMap nem nézi, és nem is nagyon teheti meg, hogy ne növelje magát, amikor kezd tele lenni, mert akkor viszont tele lesz, és akkor végtelen ciklusba kerül. Azért ez érdekes. Szét lehet hajtani a ThreadLocalMap-et?)

A másik, hogy azzal, hogy a WeakReference<ThreadLocal> leszármazottja azt éri el, hogy maga a hash tábla, mint referencia ne gátolja meg a ThreadLocal változó összegyűjtését, ha már semmi más nem hivatkozik rá. Ilyenkor a GC összegyűjti, és a gyenge referencia get() metódusa null-t ad vissza. Más szavakkal, a ThreadLocalMap-t nem használjuk a ThreadLocal változók tárolására. A ThreadLocal változók ebben a map-ben a kulcsok. Ha elveszítjük a kulcsot, nincs rá referenciánk, akkor elveszítjük a hozzá rendelt értéket is, és akkor a GC begyűjti. Ez szuper jó, mert így nem kell külön gondoskodnunk arról, hogy a ThreadLocalMap-ból is töröljük a ThreadLocal változókat. Viszont a map algoritmusa bonyolódik, mert előfordul, hogy olyan entry-t talál, amelyik (mint gyenge referencia) megszűnt objektumra mutat(na), azaz az Entry get() metódusa null-rt-ket ad vissza (stale entry). Amikor ilyennek találkozik, akkor azt törli, viszont ilyenkor minden olyan elemet, amelyik a táblában ez után az elem után jön meg kell vizsgálni, hogy valóban abba a cellába való-e, mint amelyikben van, vagy csak azért került oda, mert az az entry, amelyik már nem létezik és éppen most töröltük kitúrta őt az eredeti helyéről direkt módon, vagy úgy, hogy egy elemet kitúrt és az került arra a helyre, amire ez az elem került volna és így tovább.. Az ilyeneket egészen addig kell keresni, amíg egy üres cellát nem találunk. Ez után már nem lehet olyan érték, ami a most törölt elem miatt lett kitúrva, mert ha lenne, akkor annak itt kellene lennie. Természetesen a tömböt “modulo” kell végigjárni, azaz ha a végére értünk, akkor kezdeni kell az elejéről.

Tovább nézve a kódot találunk egy olyan sort, amelyik

private static final int INITIAL_CAPACITY = 16;

azt mondja, hogy a hash tábla kezdő mérete 16 legyen. A következő kódrészlet egy metódus:

        private void setThreshold(int len) {
            threshold = len * 2 / 3;
        }

Mivel a threshold értékét sehol máshol nem állítja a kód, ezért azt lehet állítani, hogy az minden esetben a hash tábla méretének kétharmada.

Hogyan történik a hash kód számítása, amit a map indexeléséhez használ a ThreadMap? A map-ek általában az index-nek használt objektumok hash kódját használják, amit a hashCode ad vissza. No a ThreadLocalMap nem ezt teszi. Minden egyes ThreadLocal objektumnak van egy threadLocalHashCode mezője (ennek beállításáról mindjárt), és ezt használja:

int i = key.threadLocalHashCode &amp; (len-1);

A threadLocalHashCode mezőt az új ThreadLocal objektum létrehozásakor a

private final int threadLocalHashCode = nextHashCode();

sor hozza létre, a nextHashCode() pedig igen egyszerű:

    private static AtomicInteger nextHashCode =
        new AtomicInteger();

    private static final int HASH_INCREMENT = 0x61c88647;

    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }

(Mekkorát kurjantana a cseksztájl, hogy magic konstans, és milyen igaza lenne! Amúgy nem is kurjantana, mert konstans definícióban van, és nem kód közé rejtve.) Miért olyan érdekes ez a mágikus szám? Nos azért, mert ha elkezdjük összeadogatni modulo 16, vagy modulo 32, vagy modulo 64 és így tovább, akkor végigmegy az összes lehetséges értéken, anélkül, hogy bármelyik értékre egynél többször lépne. (Nem olyan nagy kunszt ilyet találni egyébként, az 1 rögtön ilyen.) Írtam is rögvest egy kis kódot is, ami ezt ellenőrzi:

package com.verhas.hashtest;

import java.util.concurrent.atomic.AtomicInteger;

import org.junit.Test;

import junit.framework.TestCase;

public class TestHashMagicCode extends TestCase {

	private static final int HASH_INCREMENT = 0x61c88647;
	private static AtomicInteger nextHashCode;

	private static int nextHashCode() {
		return nextHashCode.getAndAdd(HASH_INCREMENT);
	}

	@Test
	public void testHashMagicCode() {
		int hashSize = 16;
		nextHashCode = new AtomicInteger();
		while (hashSize != 0) {
			boolean failed = false;
			int[] arr = new int[hashSize];
			for (int i = 0; i &lt; hashSize &amp;&amp; !failed; i++) {
				int thisCode = nextHashCode()  &amp; (hashSize-1);
				if (arr[thisCode] != 0) {
					System.out.println(&quot;Failed for &quot; + hashSize + &quot; at &quot; + i
							+ &quot; from &quot; + arr[thisCode]);
					failed = true;
				} else {
					arr[thisCode] = i;
				}
			}
			if (!failed) {
				System.out.println(&quot;For &quot; + hashSize + &quot; it is collision free&quot;);
			}
			hashSize &lt;&lt;= 1;
		}

	}

}

Hogy mit írt ki?

For 16 it is collision free
For 32 it is collision free
For 64 it is collision free
For 128 it is collision free
For 256 it is collision free
For 512 it is collision free
For 1024 it is collision free
For 2048 it is collision free
For 4096 it is collision free
For 8192 it is collision free
For 16384 it is collision free
For 32768 it is collision free
For 65536 it is collision free
For 131072 it is collision free
For 262144 it is collision free
For 524288 it is collision free
For 1048576 it is collision free
For 2097152 it is collision free
For 4194304 it is collision free
For 8388608 it is collision free
For 16777216 it is collision free
For 33554432 it is collision free
For 67108864 it is collision free
For 134217728 it is collision free

… aztán elfogyott a heap.

Ez eddig szuper, de hogyan jön ebből a 9?

Nézzük meg, hogy hogyan helyez el a ThreadLocalMap egy új elemet a map-ben:

 private void set(ThreadLocal key, Object value) {
            Entry[] tab = table;
            int len = tab.length;
            int i = key.threadLocalHashCode &amp; (len-1);

            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                ThreadLocal k = e.get();

                if (k == key) {
                    e.value = value;
                    return;
                }

                if (k == null) {
                    replaceStaleEntry(key, value, i);
                    return;
                }
            }

            tab[i] = new Entry(key, value);
            int sz = ++size;
            if (!cleanSomeSlots(i, sz) &amp;&amp; sz &gt;= threshold)
                rehash();
        }

Ha olyan hash értéket kapunk, amelyik még nem volt, akkor nem megy bele a ciklusba, amelyik szabad helyet keres, és ha sz (sic! szize) nem nagyobb vagy egyenlő, mint threshold, akkor nem is próbálja méretezni a táblát, jó az akkorának, amekkora volt. Ha pedig a tábla mérete a kezdetekkor 16, akkor treshold értéke 10, vagyis 9 elemig jók vagyunk.

Egyedül a cleanSomeSlots() hívás lehet zavaró, és időt pazarló. Ez azt csinálja, hogy minden egyes új érték beírásakor takarítja egy kicsit a táblát. Akkor is ha van elég hely. Ez a takarítás log_2size lépést hajt végre maximum. Maximum 9 esetén ez 3. A beállított cella utáni három mezőt megnézi, hogy üresek-e, és ha nem üresek, akkor a hivatkozó ThreadLocal objektum él-e még, vagy a GC már begyűjtötte. Ha már nem él az objektum, akkor kitörli, és ez fájdalmas lehet, mert ilyenkor elindul a következő elemeket megkeresni és átpakolni a saját helyükre. Ennek a kódja csak a teljesség kedvéért:

        private int expungeStaleEntry(int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;

            // expunge entry at staleSlot
            tab[staleSlot].value = null;
            tab[staleSlot] = null;
            size--;

            // Rehash until we encounter null
            Entry e;
            int i;
            for (i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal k = e.get();
                if (k == null) {
                    e.value = null;
                    tab[i] = null;
                    size--;
                } else {
                    int h = k.threadLocalHashCode &amp; (len - 1);
                    if (h != i) {
                        tab[i] = null;

                        // Unlike Knuth 6.4 Algorithm R, we must scan until
                        // null because multiple entries could have been stale.
                        while (tab[h] != null)
                            h = nextIndex(h, len);
                        tab[h] = e;
                    }
                }
            }
            return i;
        }

Összefoglalás

Ha tehát azt akarjuk, hogy gyors legyen a ThreadLocal, akkor ne használjunk többet, mint 9. Ha nagyon kell, akkor használjunk többet, de hozzuk létre az elején mindet, és amikor elindul egy szál, akkor set-eljük be az összeset, mielőtt belekezdünk abba a részbe, amelyikben nem akarjuk, hogy szöszöljön. Vigyázzunk a ThreadLocal objektumokra, amúgy is általában singleton, static objektumok, ne gyűjtse be őket a GC, mert akkor a ThreadLocalMap is elkezd rendezkedni, amikor stale entry-t talál.

És végül, de nem utolsó sorban: a ThreadLocal-ra, mint az osztálybetöltőre is igaz: ha ezt akarod használni, gondolkodj el azon, hogy nem keretrendszert írsz-e éppen, és ha rájöttél, hogy de igen, akkor ülj le a sarokba, és várd meg amíg elmúlik.

7 responses to “Miért ne legyen több, mint 9 thread lokál változónk?

  1. KB december 28, 2012 10:34 de.

    A map átszervezés “relatíve sok” költsége mennyi is igazából?

  2. v december 28, 2012 5:23 du.

    A map átszervezése ilyen esetekben két lépésben történik. Az első lépésben az expungeStaleEntries metódus hajtódik végre, amelyik kitakarít minden olyan elemet, amelyik kulcsára a gyenge referencia már null-t ad vissza. A kitakarítás során, amikor egy hash tábla elem null lesz, végig kell menni a következő elemeken is, hogy azok nem azért kerültek-e oda, mert az az elem amit éppen most pucolunk ki, az már foglalt volt. Ezzel a hash tábla méretével arányos idő lesz az expungeStaleEntries végrehajtása.

    Ezt követően, ha az előbbiekkel nem szabadult fel elég slot, akkor a resize metódus fog végrehajtódni. Ez lefoglal egy kétszer akkora táblát, mint amekkora a jelenlegi, és oda átpakolja az egyes elemeket. Ez megint a táblamérettel arányos lépés.

    • kb december 29, 2012 11:17 de.

      Azaz magyarán ha van 50 threadlocalod 9 helyett, akkor ez néhány ms-ba kerül? Mert akkor ez nem “költséges”, hanem egyszerűen van költsége, mint ahogy bárminek. Szóval erre a problémára sztem igaz, hogy tényleg felesleges túl korán szétoptimalizálni.

      Másrészt azért érdekes volt.

      • v december 29, 2012 9:25 du.

        Pontosan ennek vizsgálatára készült a két bejegyzés.

        Ugyanakkor a “néhány ms” az nem kevés, és nem is sok. A feladattól függ. Elképzelhető olyan feladat, ahol egy metódus lefutása maximum néhány ms lehet. Ilyenkor “néhány ms” sok is lehet.

  3. Pitta december 29, 2012 2:18 de.

    Nagyon részletes blogbejegyzés, köszi! Viszont erősen kétlem, hogy a ThreadLocalok létrehozásának lenne akkor impactja, hogy érdemes legyen vele foglalkozni (úgyis static lesz és szálból sem hozzunk létre sokmilliót, mert ott vannak a poolok).

    • v december 29, 2012 2:26 de.

      Szívesen. Élvezem a bejegyzések írását is, és a kommentek olvasását, illetve megválaszolását is. Sokat tanulok közben, nem csak Java-t.

      Ami azt a kérdést illeti, hogy érdemes-e ezzel foglalkozni: az előző bejegyzésben szerepelt, hogy a prekoncepció az volt, hogy lassú, és ez a két bejegyzés éppen arról szólt, hogy igazából nem az.

  4. Botond január 2, 2013 3:16 du.

    Az “érdemes-e ilyesmikkel foglalkozni” kérdéskörhöz csak annyit tennék hozzá, hogy szerintem sok esetben még ha a vizsgálat közvetlen hozadéka lényegében elhanyagolható is, maga a kutatás (avagy lustábbak /mint ebben az esetben én magam is/ számára annak követése) sok ismeretet, újabb nézőpontokat adhat. Elképzelhető, hogy a ThreadLocal korlátait soha nem fogom feszegetni, de a cikkből sokat tanultam, amiért külön köszönet a szerzőnek 🙂

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s

%d blogger ezt kedveli: