tifyty

pure Java, what else ?

Objektum Internálás

Ez a cikk az eredeti angol nyelvű cikk alapján készült.

A Java a string konstansokat egy string medencében tárolja, mégpedig mindegyik stringet pontosan egyszer. Azaz, ha

String a = "I am a string";
String b = "I am a string";

akkor a két változó a és b ugyanarra a stringre fog mutatni. Nem csak azonos lesz a két string, azaz nem csak hogy az equal() metódus eredménye lesz igaz, de pontosan ugyanarra a string objektumra “mutat” a két változó. Java-ban megfogalmazva: a == b. Ez azonban csak stringek-re, kis Integer és Long értékekre igaz. Más objektumokra általában nem igaz, hogy ha ugyanaz az értékük, akkor azonosak is lennének. Ez néha kellemetlen. Például ha előveszünk egy objektumot egy perzisztencia tárolóból (adatbázis). Ha ugyanazt a rekordot többször is elővesszük, mondjuk mert nem tudja a program logika, hogy már elővettük korábban, akkor jó lenne, ha nem egy másolatot kapnánk minden egyes esetben, hanem ugyanazt az objektumot. Más szavakkal: ha ugyanazt az objektumot veszem elő a perzisztenciából akkor ugyanazt az objektumot akarom megkapni a memóriában is. Néhány perzisztencia réteg ezt megteszi magától. Például a JPA implementációk ezt a mintát követik. Más esetekben viszont az alkalmazás szintjén kell ezt megtenni.

Ebben a cikkben részletezek egy egyszerű intern pool (belső medence) implementációt, amelyik a stackoverflow topics cikkben is megtalálható. Ami plusz ebben a cikkben, hogy részletesen leírom a tervezési megfontolásokat is.

Ojjektum medence

az ellen nem véd

Az internáláshoz kell egy objektum medence. Amikor van egy új objektumunk, akkor megnézzük, hogy az objektum medencében benne van-e már egy olyan objektum ami egyenlő a miénkkel, és ha igen, akkor azt használjuk, a miénket pedig eldobjuk. Ha még nincs ilyen objektum a medencében, akkor beletesszük, és használjuk.

Két komoly dologgal kell foglalkozni amikor ezt megvalósítjuk:

  • szemétgyűjtés
  • sokszálú környezet

Amikor az objektumra már nincs szükség, akkor ki kell dobni a medencéből. Ezt a kidobást megteheti az alkalmazás is, de ez felesleges és elavult megközelítés. A Java-ban van szemétgyűjtő, ez az egyik nagy előnye a C++-szal szemben, és ha már van, akkor használjuk. Hagyjuk, hogy a szemétgyűjtő gyűjtse be az objektumokat. Hogy ezt megtehesse nem szabad erős referenciákat tárolnunk az objektumokhoz.

Referenciák

Ha tudod, hogy mi a puha, gyenge és fantom referencia, akkor ugorj a következő fejezetre. Ha nem, akkor sokkal szerencsésebb vagy, mint a csak angolul olvasók, mert itt van egy teljes cikk ezekről magyarul, míg az angol verzióban csak egy rövid kis fejezetben foglaltam össze, hogy mik ezek. Viszont angolul sokkal több helyen megvan egyébként is. Ezért meg ők a szerencsések. Mi mindannyian szerencsések vagyunk.

A JDK-ban van egy osztály java.lang.ref.Reference néven és van másik osztály, amelyek ezt az osztályt kiterjesztik:

  1. PhantomReference
  2. WeakReference and
  3. SoftReference

Ha elolvastad a dokumentációt, esetleg az egy évvel ezelőtti cikkemet, akkor valószínűleg érzed, hogy itt most a medence megvalósításhoz gyenge referenciák kellenek majd. Fantom nem lehet, hiszen azon keresztül nem lehet az objektumhoz hozzáférni, márpedig a medencéből kellenek az objektumok. A puha sem megfelelő, mert ha már nem kell senki másnak, akkor minek tartsuk az objektumot a medencében. Majd ha újra bejön, akkor újra beletesszük. Amúgy meg a puha referencia használata általában is ellenjavallt: ha cache tárolót készítünk (nem készítünk, hanem meglevő keretrendszert használunk) akkor sem kellene a Java rendszerre bízni, hogy mikor mit eviktál (dob ki). Az ilyesmit hatékonyabban elintézi a cash cache implementáció.

A gyenge referencia pont megfelelő, mert azon keresztül el lehet érni az objektumot, de nem befolyásolja a szemétgyűjtő működését.

WeakHashMap

Nem a gyenge referenciát fogjuk direktben használni, hanem a WeakHashMap-et, ami egy olyan Map, amelyiknek a kulcsai gyenge referenciát tartalmaznak a kulcs objektumokra. Amikor internálni akarunk egy objektumot, akkor összehasonlítjuk a medencében levő objektumokkal, és ha valamelyikkel egyenlő (equal) akkor megtaláltuk. A Map pontosan ezt teszi. Az pedig, hogy csak gyenge referenciákat tart a kulcsok felé lehetővé teszi, hogy ha az objektum már nem kell senkinek, akkor a GC begyűjthesse.

Most már tudunk keresni, ami jó. De nem elég keresni: találni is kell. A Map esetében a kulcsra keresünk, és egy értéket találunk. Ebben az esetben az érték ugyanaz az objektum, mint a kulcs. De magát az objektumot nem helyezhetjük be a map-ve értékként, mert akkor van egy erős referenciánk az objektumra a map-ból és így a GC nem tudja begyűjteni, ha már nem kell senkinek. Ezért magunknak létre kell hozni egy gyenge referenciát, és azt tenni el, mint értéket.

WeakPool

Először csak egy gyenge medencét készítünk, amelyik nem rakja el az objektumot, ha nem találta meg. Egyszerűen csak megmondja, hogy van-e ilyen objektum a medencében amilyent keresünk, és ha van, akkor visszaadja. Ha meg nincs, akkor beletehetjük, de ő maga nem teszi bele magától. Egy osztály csináljon csak egy dolgot.

Itt a forráskód. Ez csak annyit mond, hogy ha az objektum amit keresünk benne van a gyenge map-ben, és meg van maga az objektum is, nem csak a gyenge referencia, akkor a get(actualObject) azt vissza fogja adni. Ha nincs benne a map-ben, vagy már csak a referencia van meg (mert pont most ledarálta a gc), akkor null-t ad vissza. A put() meg elteszi az értéket.

public class WeakPool<T> {
  private final WeakHashMap<T, WeakReference<T>> pool = new WeakHashMap<T, WeakReference<T>>();
  public T get(T object){
      final T res;
      WeakReference<T> ref = pool.get(object);
      if (ref != null) {
          res = ref.get();
      }else{
          res = null;
      }
      return res;
  }
  public void put(T object){
      pool.put(object, new WeakReference<T>(object));
  }
}

InternPool

A feladatra a teljes megoldás egy internáló medence (intern pool), amelyet nem is olyan nehéz implementálni ha megvan a gyenge medencénk, a WeakPool. Az InternPool tartalmaz egy gyenge medencét és ezen kívül egyetlen szinkronizált metódus van csak az az osztályban.

public class InternPool<T> {
  private final WeakPool<T> pool = new WeakPool<T>();
  public synchronized T intern(T object) {
    T res = pool.get(object);
    if (res == null) {
        pool.put(object);
        res = object;
    }
    return res;
  }
}

A metódus megnézi, hogy a keresett objektummal egyenlő objektum van-e a medencében, és ha benne van, akkor visszaadja azt, ami a medencében van. Ha nincs benne, akkor beleteszi, és úgy adja vissza a most már a medencében található objektumot.

Multi-thread

A metódusnak szinkronizáltnak kell lennie, hogy biztosítsuk, hogy a pool-ban való keresés és az új objektum belehelyezése atomi művelet legyen. A szinkronizálás nélkül előfordulhatna, hogy két szál is azt találja, hogy nincs az általuk keresettel egyenlő objektum a pool-ban, és mind a kettő berakja a saját verzióját, ami akkor gond, ha ezek egymással is egyenlőek. Ebben az esetben amelyik másodiknak rakja el az objektumot annak a változata lesz a pool-ban, az első viszont a sajátját használja, mint intern-ed verziót. A szinkronizálás megoldja ezt a problémát.

Versengés a szemétgyűjtővel

Annak ellenére, hogy az alkalmazás különböző szálai nem okozhatnak gondot, mivel gyenge referenciákat használunk végig kell gondolni, hogy nem akadhatunk-e össze a szemétgyűjtővel.

Előfordulhat, hogy a gyenge map-ból megkapjuk a gyenge referenciát az objektumunkhoz, de mire a következő utasításban erre meghívjuk a get() metódust addigra az már null-t ad vissza, mert közben az objektumot begyűjtötte a szemetes. Ez még akkor is lehetséges ha a gyenge map úgy van implementálva, hogy null-t adjon vissza ha olyan objektumra keresünk, amelyiket begyűjtött a szemetes. (Egyébként így van.)

Ebben az esetben azonban a WeakPool implementáció null-t ad vissza. Semmi probléma. Így az ezt használó InternPool sem küzd ilyen problémával.

Ha megnézzük azokat a megoldásokat, amelyeket a fent említett stackoverflow cikkben, adtak, az következő kódot láthatjuk:

public class InternPool<T> {

    private WeakHashMap<T, WeakReference<T>> pool = 
        new WeakHashMap<T, WeakReference<T>>();

    public synchronized T intern(T object) {
        T res = null;
        // (The loop is needed to deal with race
        // conditions where the GC runs while we are
        // accessing the 'pool' map or the 'ref' object.)
        do {
            WeakReference<T> ref = pool.get(object);
            if (ref == null) {
                ref = new WeakReference<T>(object);
                pool.put(object, ref);
                res = object;
            } else {
                res = ref.get();
            }
        } while (res == null);
        return res;
    }
}

Ebben a megoldásban a programozó egy végtelen ciklust használ annak az esetnek a kezelésére, amikor a szemetes az objektumot éppen az ahhoz való hozzáférés közben gyűjti be, de a map még visszaadta a gyenge referenciát. Nem valószínű, hogy a ciklus végtelen sokszor lefusson (enyhe irónia), sőt valószínűleg az esetek kozmikusan nagy százalékában teljesítmény gondot sem okoz. Ennek ellenére a kód összetett, nem triviális a megértése.

Tanulság: egy osztály, egy feladat. Bontsuk szét a feladatot alap műveletekre, és az esetek igen nagy százalékában egyszerűbb kódot kapunk.

Sajnos még a Google guava projektje is ezt a ciklusos algoritmust használja. Amint azt az eredeti cikk JCG szindikált megjelenésére írta SH:

Why would you even create a shockingly inferior interner to Guava’s, let alone publish it in an article??
https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/collect/Interners.java?r=cb72618c27773e8aa91238eca87b5e63f08b010f#66

Vagyis: “Minek készít valaki a Guava interner megoldásánál sokkolóan gyengébb megoldást, és még publikálja is?” (Válasz az JCG cikk után angolul.)

Érdemes megnézni a Guava kódot a fenti linken, lehet belőle tanulni, annak ellenére, hogy erős meggyőződésem: nincs szükség a ciklusra a megoldáshoz, és lehet olvashatóbban is kódolni. De feladat adott: ha valaki tudja, hogy miért kell mégis a végtelen ciklus, és miért nem jó az a megoldás, amit ebben a cikkben leírtam, írja meg!

Összefoglalás

Annak ellenére, hogy a Java a string konstansokat pool-ba rakja (ráadásul a permgen-be, amíg még van olyan),
és hasonlóképpen pool-ba rakja néhány primitív típus objektum megfelelőjét néha szükséges egyéb objektumok internálása is. Ezekben az esetekben az internálás nem automatikus, az alkalmazásnak kell azt megtennie. Ez a két osztály alkalmas arra, hogy ezt megtegyük, akár másolt tésztával (copy/pasta) akár repository függőséggel

        <dependency>
          <groupId>com.javax0</groupId>
          <artifactId>intern</artifactId>
          <version>1.0.0</version>
        </dependency>

a központi maven repo-ból. A könyvtár minimális, csak ezt a két osztályt tartalmazza és Apache licensszel használható (vagyis open source erősen). A forráskód a GitHub-on található.

Szavazás

After we managed to have a pool, now lets to have a poll! (Ezt nem tudom lefordítani.) Kérlek, hogy a következő kérdésre őszintén válaszolj:

3 responses to “Objektum Internálás

  1. Zsolt János április 2, 2014 10:30 de.

    “a cash implementáció.” Tudatalatti? 🙂

  2. Bence Sarosi december 14, 2014 4:40 du.

    Zseniális cikk, ismételten, kedves kolléga úr! Köszönöm!

    De mondja, kérem, szándékosan borzolja a kedélyeimet a medence szóval? Az “internálós medence” kifejezésről nem is beszélve; nem menjünk bele, mi jut róla eszembe 😀

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: