Schenller zugriff auf Einträge in verketteter Liste

[Ano N. (oorim)]

Servus

Ich bin derzeit dabei einen Cache zusammenzufrickeln. Meine Idee war 
hier eine verkette Liste zu benutzen. Jedes der Items bekommt dabei 
einen Namen (item.name), den Zeiger aufs nächste und aufs vorherige Item 
sowie ein Alter.
Nun frage ich mich folgendes: Ich möchte auf Item25 zugreifen. Nun 
könnte ich entweder nach dem Namen suchen (strcmp) (direkt in der Liste 
oder in einem Array das Name | Adresse beinhaltet). Oder ich berechne 
die Adresse des Items aus dem Namen. Geht das überhaupt - beliebiger 
Name auf spez. Adresse? Heißt sowas nicht Hash Code?

Und: Macht eine verkettete Liste überhaupt Sinn oder wäre ein normales 
Array sinnvoller?

Vielleicht kann mir jemand weiter helfen.

[Andreas H. (andreas_h16)]

Hallo,

wenn du schnell in Bäumen suchen willst, dann implementiere z.B. einen 
B-Baum. Wikipedia liefert Links zu Beispielen. Auch im altehrwürdigen N. 
Wirth findet man Beispiele.

Einfacher ist, für die Strings einen eindeutigen Hash zu berechnen. Bei 
nicht zu vielen Daten braucht man keinen MD5! Diesen als Index einer 
Tabelle benutzen, welche dann einen Pointer auf die gesuchte 
Datenstruktur enthält.

Hier erkauft man sich Rechenzeit durch Einsatz von Speicher.

MfG,
Andreas

[U.R. Schmitt (Gast)]

Verkettete Listen machen dort Sinn wo man schnell einfügen oder löschen 
können muss und ansonsten sequentiell über die Liste iteriert.
Wenn du einen schnellen wahlfreien Zugriff auf eine eine Menge von 
Objekten haben willst, macht entweder ein sortiertes Array mit binärer 
Suche oder binäre Bäume oder eben eine Hashtabelle Sinn.
Was du jetzt implementierst hängt davon ab wie groß die Datenmenge ist, 
wieviel Aufwand du treiben willst, wie dein Kenntnisstand ist und welche 
Plattform (Speicher) du benutzt.
Bei konkreteren Fragen kann dir hier bestimmt jemand weiterhelfen.

[Ano N. (oorim)]

Geht um Cache auf einem Mikroprozessor. Große Daten, unterschiedlich oft 
benutzt, Rechenzeit wichtig, Zugriffszeit auf Speicher begrenzt.

Nun passt es mit dem Use Case gut zusammen (soweit der Plan, das möchte 
ich Untersuchen) die Daten in einem LRU Cache zu speichern.

Für Cache gibt es, soweit habe ich das glaueb ich verstanden, zwei 
Ansätze:
 - Verkettete Liste
 - Array

Der Gag: Immer wieder wenn ein neues Item kommt rutscht die Liste eins 
nach unten und das neueste kommt oben drauf. Damit sortiert sichs 
automatisch nach dem am wenigsten häufig benutzten/ältesten item.

Nun bleibt die Frage ob eine Liste oder ein Array mehr Sinn machen. Und 
egal welches davon, wie ich schnell auf das Datum zugreife ohne lange 
suchen zu müssen. Wieviele Daten es schlussendlich sind weiß ich nicht 
...

An Hash hab ich auch gedacht. Nur irgenwdie bekomme ich da gerade einen 
Knoten ins hirn ... die Application kennt nur den Namen und sagt 
"readFromCache(item25)" und bekommt dann von der Adresse xy das Datum. 
Da bekomm ich bisschen einen Knoten ins HIrn wie das verwurstet werden 
muss ...

Ah, Idee:
Array Cache
cache[1] --pointed to--> item1
cache[2] --pointed to--> item2
...

Hashe Cache
hache[1] > if accessed hash == hash in hache[1] => cache[index aktuell 
hache[] ist gesuchtes datum
usw

Und wenn ich ein Datum aus dem Cache lösche und alles nachfolgende eins 
nach oben rücke muss ich das selbe mit der hache tabelle machen richtig? 
Nur wie komm ich von cache[] auf hache[] :D

[Ano N. (oorim)]

Edit: Im Falle meines Caches kann ichs auch so machen

struct sCacheItem{
data;
NAND_memAdress; // Physikalisch echte Adresse, gleichzeitig Key
}

struct sCacheItem* aCache[MAXCACHEITEMS];

Zugriff aufs Item erfolgt dann mit suche nach er physikalisch echten 
Adresse die gleichzeitig als Key/Name dient. Bin die ganze Zeit auf dem 
Trip rumgerannt die Items nach dem als realen String zu bennnen wie sie 
auch benutzt werden - is ja ganz nett aber funktioniert nicht so 
richtig. Und da ich irgendwo die phys. echte Adresse ablegen muss kann 
ich die auch gleichzeitig als Name benutzen. Der Cache soll auf 
Applikationsebene ja eh "unsichtbar" sein und das ist er dann ja auf 
jeden fall.

[Markus J. (markusj)]

Naja, für einen Software-Cache brauchst du zweierlei:
Eine Datenstruktur die es dir erlaubt, entsprechend deiner 
Verdrängungsstrategie (du schriebst LRU) schnell Aktualisierungen 
vorzunehmen, und andererseits eine Suchstruktur mit der du die 
betreffenden Cache-Einträge schnell auffinden kannst.

Vorschlag, da du ja mit expliziten Cache-Zugriffen (readFromCache) 
arbeitest, verwende doch einfach ein Handle, das intern nur ein Pointer 
auf eine Struktur mit Adresse des Listenelements + Ursprungsadresse der 
Daten ist. Umgekehrt speichert jedes Cache-Element auch Ursprungsadresse 
+ Daten.
Wenn das Element verdrängt wurde, stimmt die Adresse des Handles mit der 
des referenzierten Cache-Elementes nicht mehr überein, das Handle ist 
ungültig.

Beispiel:

// Typdefinitionen, vereinfacht
Handle (mem_addr, *cache_element)
Cache array of CacheElement (*prev, *next, mem_addr, data)

// Anwendungscode
Handle item25;
item25.mem_addr = 42; // gewünschte Speicheradresse setzen
// ...
readFromCache(&item25); // cache_element != null && cache_element->mem_addr = handle->mem_addr ? alles ok, Cacheeintrag gültig : Cacheeintrag ungültig, nachladen

Anstelle dem Programmierer die Handles aufzudrücken könntest du auch 
intern ein Mapping Adresse->Cache-Element aufbauen, das wäre dann die 
Variante mit der schon erwähnten Hashtabelle (oder einer anderen 
assoziativen Struktur).

mfG
Markus

[Ano N. (oorim)]

Ah, sodass ich also faktisch als Anwender von vorneherein meine Items 
anlege - roh - und denen dann wenn sie in den Cache geladen werden auf 
den Eintrag im Cache zeigen lasse. Ich steh nur irgendwie noch 
gedanklich mit dem Mapping auf dem Schlauch. Das wäre die mir liebste 
Variante - also das der geneigte Anwender nur sagen muss 
"readFromCache(item25)" oder eben nur "read(item25)".

Wie sähe dann das Mapping aus? Ein array[][] mit Name vorne und Cache 
Entry in der zweiten Spalte? Andererseits isse auch egal da das alles 
irgendwie doppelt und dreifach ist. Ich weiß ja von vorne herein welche 
Items ich habe, ergo brauch die ja nur dynamisch auf den Cache zu mappen 
un gut is.

Besteht die möglichkeit Daten in einem struct "private" zu gestalten? So 
wie Funktionen in einer .c nur für die .c zugänglich gemacht werden 
indem man sie static macht.

[Markus J. (markusj)]

Ano Nym schrieb:
> Besteht die möglichkeit Daten in einem struct "private" zu gestalten? So
> wie Funktionen in einer .c nur für die .c zugänglich gemacht werden
> indem man sie static macht.

Leider nicht, auch wenn das aus softwaretechnischer Sicht wünschenswert 
wäre.
Es gibt eine Reihe von Tricks, die aber auch gewisse Einschränkungen mit 
sich bringen [1], [2], [3]

mfG
Markus

[1] 
http://stackoverflow.com/questions/1154709/how-can-i-hide-the-declaration-of-a-struct-in-c
[2] 
http://tinobox.com/wordpress/c-programming/how-to-hide-a-struct-member-in-the-c-programming-language/
Edit: Einer geht noch ...
[3] http://en.wikipedia.org/wiki/Opaque_pointer

[Andreas H. (andreas_h16)]

Hallo,

wenn alle Deine Items sowieso schon bekannt sind, dann kannst Du ja die 
Hashfunktion auf Kollisionsfreiheit und Tabellengrösse trimmen.

Nimm z.B. mal die klassischen Hashfunktionen (z.B. 
http://www.ntecs.de/projects/guugelhupf/doc/html/x435.html) und lasse 
sie über Deine Items laufen. Hast du z.B. 100 Items, wähle eine maximale 
Tabellengröße von z.B. 256 und überprüfe, wie viele Kollisionen Du bei 
den verschieden Algorithmen hast.

Laut Fazit des Artikels schneidet NEW [Bob Jenkins] für kleine Tabellen 
(hier n=8) am besten ab. Ist auch relativ leicht zu implementieren.

Falls Du 0 Kollisionen hast, ists sowieso geschenkt, dann gibt der 
berechnete Hash den Index auf die Tabelle (im einfachsten Fall Pointer 
Array auf struct { type_enum eUsed, void *pData, void wasauchimmer }.

Über Diesen Pointer greifst Du dann kollisionsfrei auf Deinen Cache zu.

Bei Kollisionen kann man ggf, die Tabellengröße erhöhen, die 
Hashfunktion optimieren, die Kollisionen verwalten oder zu dreckigen 
Tricks greifen.

>Besteht die möglichkeit Daten in einem struct "private" zu gestalten?
Private gibts ohne Speicherschutz sowieso nicht, sondern nur obfuscate. 
Das erreicht man schon, indem die Daten nicht im Header deklariert 
werden.

[Ano N. (oorim)]

Private ansich gibts nicht, aber man kann machen das die Daten nicht 
mehr sichtbar sind von außen ;) so wie static Funktionen.

Ich schau mir die Links mal an. Danke. Die Seite zu den Hash Funktionen 
hab ich schon gesehen. Denk mir aber im Moment: Ich habe eine Adresse 
die Eindeutig einem Item, einem Eintrag und einer Position im phys. 
realen Speicher vorhanden ist. Nehm ich doch einfach die un spare mir 
die Hash Tabelle.

Heißt ich implementiere jetzt zwei structs

 typedef struct
 {
  #if LinkedList
  Uint8* pNext;  /*! \var  *pNext \brief Pointer to next list entry */
  Uint8* pPrev;  /*! \var *pPrev \brief Pointer to previous list entry */
  #endif
  
  MEM_ADDR_SIZE mem_addr;    /*! \var mem_addr \brief Physically real memory adress */
  DATA_SIZE data;        /*! \var data \brief Data stored at entry */
 } s_hCacheEntry;

und

typedef struct 
{
  MEM_ADDR_SIZE mem_addr;    /*! mem_addr \brief Physically real memory adress */
  s_hCacheItem* cache_entry;  /*! cache_entry \brief Pointer to the according cache_entry */
}s_hObject;

Das erste sind die Einträge im Cache selbst, das zweite sind die Objekte 
die der Anwender in die Finger nimmt.
Lesen vom Cache geht dann über

Uint32 readData(s_hObject*, s_hCacheEntry*);

Das intern alles mit LRU und dem Cache selbst verwurstet (Daten vom 
Cache Entry werden als return übergeben, damit hat der Anwender mit dem 
Cache nicht mehr so viel zu tun).

Ich pers. finde das jetzt nicht so ungeschickt, kann mich da aber auch 
täuschen

[Andreas H. (andreas_h16)]

Ano Nym schrieb:
> Denk mir aber im Moment: Ich habe eine Adresse
> die Eindeutig einem Item, einem Eintrag und einer Position im phys.
> realen Speicher vorhanden ist. Nehm ich doch einfach die un spare mir
> die Hash Tabelle.

Entweder das ist jetzt unklar ausgedrückt oder Du verstehst den Sinn des 
Hashens nicht.

Falls mit Hashen gearbeitet wird, brauchst Du keine verkettete Liste, 
außer Du verwendest einen kollisonsfreien(!) Hash als Eingang zu binären 
oder B-Bäumen oder Skip-Lists.

Ansonsten brauchst Du eine Hash-Tabelle, Da dir der Hash ja das Bucket 
aus der Tabelle liefert, welches Deine Daten bzw. einen Zeiger auf Deine 
Daten liefert, d.h. über den Hash wird ja SCHNELL gesucht.

Bei Dir seh ich bis jetzt nur eine verkettete Liste ?!!

1. Schritt: Berechnen der Hashes
Item 0..x -> Hash 0..y  mit x=y wenn Kollisionsfrei

2. Schritt: Initialisieren der Hashtabelle, z.B. Bucket = NULL

3. Schritt: Schreiben in die Tabelle (n Zellen) mit n>=x beim Cache 
Write
bzw. Bucket(Hash(x)) = Pointer auf Cache von x

3.a.Verdrängungsstrategie: Ältesten Eintrag ggf. löschen und zugehörigen 
Hashtabelleneintrag auf NULL setzen

4. Schritt: CacheRead
Hash des gesuchten Elements berechnen, Lookup in Hashtabelle, Wenn 
Bucket <> Null, dann (*Pointer) lesen, ansonsen return Fail.

MfG,
Andreas

[Peter D. (peda)]

Eine verkettete Liste ist nur sinnvoll, wenn die Einträge immer der 
Reihe nach benutzt und ausgetragen werden.

Z.B. man hat einen Scheduler und die Einträge sind nach ihrer 
Ausführungszeit sortiert. Der Scheduler schnappt sich also immer den 
ersten Eintrag, führt ihn aus und löscht ihn. Er muß nichts mehr 
umständlich vergleichen. Das wurde schon beim Einfügen des Eintrags in 
die Liste getan.

Ansonsten ist es nur unnötiger zusätzlicher Verwaltungsaufwand, da man 
sich immer von Eintrag zu Eintrag hangeln muß.

Müssen Einträge sortiert werden, nimmt man eine einfache Liste. Diese 
enthält nur die Nummern der Einträge. Bei längeren Daten ist es 
schneller nur die Nummer des Datensatzes zu sortieren, anstatt immer die 
kompletten Datensätze umzukopieren.


Peter

[Markus J. (markusj)]

Hallo Peter und Andreas,

wenn es bei mir nicht gerade genauso ist, habt ihr etwas zu schnell 
geantwortet. Die verkettete Liste implementiert die LRU-Strategie des 
Caches, eine Navigationsstruktur existiert nur implizit durch die 
Mapping-"Objekte", die beim Laden eines Cache-Eintrages aufgesetzt 
werden müssen.

Ano Nym schrieb:
> Ich pers. finde das jetzt nicht so ungeschickt, kann mich da aber auch
> täuschen

Richtig, aber es gibt eine Einschränkung der du dir bewusst sein musst:
Diese Variante erkennt es nicht(!), wenn an zwei stellen die selbe 
Adresse in den Cache geladen wird. Es existieren dann zwei unabhängige 
Kopien und mit hoher Wahrscheinlichkeit kriegst du dann sehr hässliche 
Seiteneffekte.

mfG
Markus

PS: Bei kleineren Caches kann es effektiver sein, auf aufwändige 
Navigationsstrukturen zu verzichten und einen sequentiellen Scan 
durchzuführen. Solche Randfälle sollte man aber bei Verdacht vorab 
überprüfen und nicht einfach darauf spekulieren.

[Ano N. (oorim)]

Peter Dannegger schrieb:
> Eine verkettete Liste ist nur sinnvoll, wenn die Einträge immer der
> Reihe nach benutzt und ausgetragen werden.
>
> Z.B. man hat einen Scheduler und die Einträge sind nach ihrer
> Ausführungszeit sortiert. Der Scheduler schnappt sich also immer den
> ersten Eintrag, führt ihn aus und löscht ihn. Er muß nichts mehr
> umständlich vergleichen. Das wurde schon beim Einfügen des Eintrags in
> die Liste getan.
>
> Ansonsten ist es nur unnötiger zusätzlicher Verwaltungsaufwand, da man
> sich immer von Eintrag zu Eintrag hangeln muß.
>
> Müssen Einträge sortiert werden, nimmt man eine einfache Liste. Diese
> enthält nur die Nummern der Einträge. Bei längeren Daten ist es
> schneller nur die Nummer des Datensatzes zu sortieren, anstatt immer die
> kompletten Datensätze umzukopieren.
>
>
> Peter

Wie gesagt, das #if LinkedList #endif is nur prophylaktisch drin falls 
ichs mit Ketter lösen wollte. Hab dann im späteren Verlauf noch ein 
weiteres Strukt

typedef struct
{ /* Vereinfacht */
numEntries
s_hCacheEntries* CacheTable[MAX_NUM_OF_ENTRIES]
}s_hChecksum

machs also mit nem Array. Als Key für die Daten nutz ich die Adresse für 
den realen speicher. Heißt:

readCache(Object, Cache) // Vereinfacht!
{
  for(sizeof(Cache)
  {
   if(Cache->CacheTable[i]->mem_addr = Object->mem_addr)
   {
    _do_something
   }
  }
}

Und damit vergleich ich wieder nur Zahlen und hab keine extra Tabelle 
für das Mapping. Im grunde müsste das doch jetzt so tun wie mit Hashin 
nur ohne Hashing oder?

[Karl H. (kbuchegg)]

Ano Nym schrieb:

> Und damit vergleich ich wieder nur Zahlen und hab keine extra Tabelle
> für das Mapping. Im grunde müsste das doch jetzt so tun wie mit Hashin
> nur ohne Hashing oder?

Nicht wirklich.

Der Trick beim Hashen besteht ja darin, dass man nicht lange suchen 
muss, sondern errechnen kann, wo ein Eintrag ist, wenn er denn in der 
Liste ist.

Das ganze ist allerdings immer auch davon abhängig, wie gross denn dein 
Sucharray ist. Bei wenigen Einträgen kann lineares Suchen, so wie du es 
betreibst, schneller sein als alles andere. Ganz einfach deshalb, weil 
deine Schleife extrem eng ist und es de facto innerhalb der Schleife 
nichts zu tun gibt ausser zu vergleichen. Wenn du erst mal vom 
Suchbegriff einen Hash-Code ausrechnen musst, dann kostet das Ausrechnen 
ja auch Zeit und in der Zeit kann die enge Suchschleife schon einige 
Einträge abklappern.

Wie überhaupt die Kunst beim Cachen darin besteht einen Kompromiss zu 
finden zwischen dem Aufwand den man treiben will (und der natürlich Zeit 
kostet) und der Zeit die man durchs cachen einspart. Ist der Aufwand 
höher als die eingesparte Zeit, dann hat man es übertrieben.

> Und damit vergleich ich wieder nur Zahlen und hab keine extra
> Tabelle für das Mapping.

Dann überleg dir mal, was du alles tu musst um in deinem Array eine LRU 
Strategie zu implementieren. Was muss alles passieren wenn ein Eintrag 
aus dem Cache rausfliegt.

[Ano N. (oorim)]

Stimmt beim Hashen muss ich nicht linear suchen. Zur Zeit weiß ich noch 
nicht wieviel Elemente unser Use Case vorsieht - ich denke aber mal 
<=100.

EIn erster Entwurf meiner implementierung schaut wiefolgt aus:

uint32 readData(s_hObject* p_object,s_hCache* p_cache)
{
  uint8 u8index;
  uint8 error;
  error = 0;
  
  for(u8index = 0; u8index>=p_cache->numEntries; u8index++)
  {
    /* Compare adress in object with cache index */
    if(p_object->mem_addr == p_cache->CacheTable[u8index]->mem_addr)
    { /* Cache hit */

    break;
    }
  }
  
  if(u8index>=p_cache->numEntries)
  { /* Cache hit */
    #if CountCacheHitMiss
      cache_hit++;
    #endif
  }
  /* Cache miss! */
  {
    #if CountCacheHitMiss
      cache_miss++;
    #endif
    error = AddCacheEntry(p_cache, object->mem_addr);
  }
  
  return cache->CacheTable[u8index]->data
}

und

static char AddCacheEntry(s_hCache* Cache,Uint32 mem_addr)
{
  uint8 u8index;
  DATA_SIZE data;
  
  // Read Data from NAND  
  if(Cache->numEntries >= MAX_NUM_CACHE_ENTRIES) // Cache is full
  {
    DeleteCacheEntry(Cache->CacheTable[MAX_NUM_CACHE_ENTRIES]);
  }  
  else if(Cache->numEntries <= MAX_NUM_CACHE_ENTRIES) // Cache is not full
  {
    Cache->numEntries++;
  }
  
  // Move list down from 1 to End
  for(u8index = numEntries; u8index>1;u8index--)
  {
    Cache->CacheTable[u8index]=Cache->CacheTable[u8index-1];
  }
  
  Cache->CacheTable[0] = GenerateCacheEntry(mem_addr);
  
  if(Cache->CacheTable[0] == NULL)
  { /* Error allocating! */
    return 1;
  }
  else
  {
    Cache->CacheTable[0]->data = data;
  }
    
  return 0;
}

Ist recht straight forward. Mein Gedanke: Wenn ich immer das unterste 
rauszieh, lösch, die Tabelle eins nach unten rück und das benutzte nach 
ganz oben einfüge ist das älteste/am wenigsten Benutzt immer unten -> es 
sortiert sich von selbst.
Was noch fehlt ist bei einem Cache hit die Tabelle ebenfalls 
umzusortieren sodass das benutzt wieder ganz oben ist. Ansonsten ist es 
wirklich als erster Draft zu sehen, REchtschreibfehler dürfen behalten 
werden

[Andreas H. (andreas_h16)]

>Autor: Ano Nym (oorim)
>Datum: 22.02.2011 11:37
>Geht um Cache auf einem Mikroprozessor. Große Daten, unterschiedlich oft
>benutzt, Rechenzeit wichtig, Zugriffszeit auf Speicher begrenzt.

Hmmm, irgendwie passen linear suchen und Rechenzeit wichtig, nicht gut 
zusammen.

Außerdem seh ich die Verdrängungsstrategie nicht in Deinem Code oder 
soll das das hier sein:
>Ist recht straight forward. Mein Gedanke: Wenn ich immer das unterste
>rauszieh, lösch, die Tabelle eins nach unten rück und das benutzte nach
>ganz oben einfüge ist das älteste/am wenigsten Benutzt immer unten -> es
>sortiert sich von selbst.
>Was noch fehlt ist bei einem Cache hit die Tabelle ebenfalls
>umzusortieren sodass das benutzt wieder ganz oben ist. Ansonsten ist es
>wirklich als erster Draft zu sehen, REchtschreibfehler dürfen behalten
>werden
D.h. Du willst die Tabelle bei jedem Hit umsortieren ??
>Rechenzeit wichtig
Rechenzeit eher unwichtig, oder?

Vorschlag meinerseits: Nachdem Du ja mit einer Use Case Analyse schon 
sehr gut angefangen hast, springe nicht vom Start zum Ziel.

Auch wenn manche Leute das im Kopf machen können, ist doch in jedem 
ernstzunehmenden Entwicklungsprozess ein Designschritt zwischen Analyse 
und Programmierung (z.B. OOA->OOD->OOP), so rapid prototyping kann das 
ja gar nicht sein.

Bevor Du also ans Coden denkst, überlege Dir mal ein Design KOMPLETT 
durch, welches zu den Anforderungen passt. C-Strukturen und Codes kommen 
am Schluss.

Grundsätzliche Fragestellungen im Design sind z.B. auch, müssen die 
gecacheten Items wirklich über einen Namen gesucht werden
>entweder nach dem Namen suchen (strcmp).... Oder ich berechne
die Adresse des Items aus dem Namen

... oder kann man den Items vielleicht ein eindeutiges Token zuordnen ? 
Dann kann man sich das ganze hashen bzw. die Implementierung der 
assoziativen Arrays sparen.

Viel Spaß noch

[Ano N. (oorim)]

Jup im moment sortier ich nach jedem hit um. Das ist Rechenaufwändiger 
als wenn ich die einzelnen Elemente mit einer Variable altern lassen 
würde und einfach immer das älteste weg werf. Ist halt als erstes 
Gedankenmodell zu sehen.

Ansonsten, zum eindeutigen Token: Warum nicht einfach die Adresse die 
zum Platz im Speicher gehört her nehmen? Man könnte damit ja auch auf 
das Objekt Struct verzichten, das beinhaltet ja im Grunde nur die 
Adresse.

Ansonsten wäre ein Optimierungsschritt: Hash statt linearer suche. Das 
hab ich allerdings noch nicht völlig Verstanden und damit auch nicht 
integriert.

Ansonsten hab ich zu ziemlich jedem Algo bis auf die Page basierten was 
raus geschrieben. Ich hab mir zu dem obigen GEdanken gemacht welche 
Schnittstellen ich brauche und wie das Programm abläuft. Ist zwar immer 
noch mehr oder weniger rapid prototyping aber so what :)

Aber bis auf die ineffizienten Stellen, so schwachsinnig ist das was ich 
gezaubert habe erstmal nicht oder?

[Andreas H. (andreas_h16)]

Ano Nym schrieb:
> Ansonsten, zum eindeutigen Token: Warum nicht einfach die Adresse die
> zum Platz im Speicher gehört her nehmen? Man könnte damit ja auch auf
> das Objekt Struct verzichten, das beinhaltet ja im Grunde nur die
> Adresse.

Das mit der Adresse klingt gut und entspräche wohl einem eindeutigem 
Token, aber Du hast ja in Deinem ersten Post gleich mit
>strcmp
angefangen, so daß man annehmen konnte, Dein Suchschlüssel wäre ein 
String bzw. eine Kombination aus String+Adresse.

Wenn Du jetzt aus Deiner Adresse einen eindeutigen Platz in einer 
Cachetabelle (enspricht im Grunde einem simplen Hashen und einer 
Hashtabelle) berechnen kannst, dann brauchst Du keine verketteten Listen 
und keine lineare Suche und kannst Dich voll auf Verdrängungsstrategie, 
Fragmentierung, etc. konzentrieren.

>Aber bis auf die ineffizienten Stellen, so schwachsinnig ist das was ich
gezaubert habe erstmal nicht oder?
Das ergibt sich leider nur aus einen Vergleich der optimalen Lösung des 
Problems zu Deinem Ansatz.

P.S. Ist das eine Semesterarbeit ?

[Ano N. (oorim)]

Nein, istk eine Semesterarbeit. Bin durch mit studieren.


Ich habe oben strcmp geschrieben, richtig. Das war noch aus der Idee 
geboren zu sagen "readCache("Item25")". Ist aber revidiert da Käse: Man 
erstelle Objekte des Typs Object item25 und übergebe die an readCache. 
Resultat: Man hantiert mit Objekten die nicht so abstrakt sind wie die 
bloße Adresse und man kann in dieses Objekt ein eindeutiges Token 
werfen.

Ansonsten: Verkettete Liste benutz ich im moment nicht. Ich hab zwar ein 
#if LinkedList drin aber das ist, wie gesagt, nur prophylaktisch als 
"falls". Im moment ist es ein einfaches Array aus Pointern zu den Entrys

typedef struct
{
  uint8 numEntries;  /*! \var numEntries \brief Actual number of used entries inside the cache */
  s_hCacheEntry* CacheTable[MAX_NUM_CACHE_ENTRIES]; /*! \var CacheTable[] \brief The cache itself */
}s_hCache;

Punkte die man def. optimieren könnte:
- Berechnung der Position eines Items im Cache anhand eines eindeutigen 
Tokens (in dem Fall die phys. reale Adresse im Speicher).
- Ggf. wegfall des Objektstructs - optional, kommt drauf an ob man ads 
eine oder das andere hübscher findet ;)
- Nicht den Cache ständig umsortieren: Einsatz von einer "age-variable" 
um das älteste zu identifizieren. Kann im struct CacheEntry eingeführt 
werden. Um herauszufinden welches das älteste ist entweder einen 
schnellen Sortieralgo einführen

[Andreas H. (andreas_h16)]

Ano Nym schrieb:
> - Nicht den Cache ständig umsortieren: Einsatz von einer "age-variable"
> um das älteste zu identifizieren. Kann im struct CacheEntry eingeführt
> werden. Um herauszufinden welches das älteste ist entweder einen
> schnellen Sortieralgo einführen

Wenn du eine Age-Variable benutzt, dann hast Du zwar keinen echten LRU 
Algorithmus mehr, sondern nur noch einen NFU (Not frequently used), aber 
Du sparst dir das Umsortieren bzw. die verketteten Listen, die Du bei 
einem LRU gebraucht hättest.

So hast Du im Fall des Schreibens in einen vollen Caches eine lineare 
Suche nach dem ältesten Element.

Den Aufwand eines klassischen LRU hätte ich sowieso nie getrieben, aber 
das entscheidet sich schon vor der Designphase in der Analysephase 
deiner Architektur.

[Ano N. (oorim)]

Warum ist die Geschichte mit dem Altern nicht mehr LRU? Recently = 
jüngst. Heißt, je länger ein Eintrag nicht benutzt wird, desto "least 
recently" ist er benutzt und desto älter ist er.

Was du meinst wäre das Gegenteil von Least FREQUENTLY used, dann müste 
ich mir merken wie häufig ein Eintrag in Abhängigkeit der Zeit benutzt 
wird --> Aufwändiger.

Ansonsten ist der Use Case im moment so, dass es Einträge die häufiger 
benutzt werden und welche die weniger häufig benutzt werden, bzw. es 
länger dauert bis sie wieder in Kraft treten. Ich weiß noch nicht wie 
groß der Cache sein muss und wie häufig "häufig" ist. Aber vom 
Grundverständnis aus der Dikussion her klingt LRU in Kombination mit 
einem zeitlichen Trigger der das älteste wegwirft um Leichen zu 
vermeiden Sinnvoll.

Ansonsten schien mir meine Lösung als eine gängige (man findet am 
meisten dazu) und als eine weniger komplexe...

[Andreas H. (andreas_h16)]

Ano Nym schrieb:
> Warum ist die Geschichte mit dem Altern nicht mehr LRU? Recently =
> jüngst. Heißt, je länger ein Eintrag nicht benutzt wird, desto "least
> recently" ist er benutzt und desto älter ist er.
Die Bedingung ist zwar notwendig für LRU aber nicht hinreichend.

Beispiel:
Bei einer Age-Variable wird z.B im Timer-Interrupt hochgezählt, wie alt 
ein Eintrag ist oder man merkt sich in der Cache-Tabelle dazu einen 
groben Timertick (Deshalb Age).

Aufgrund der groben ungenauen Werte, kann es vorkommen, dass zwei oder 
mehr Elemente das selbe Alter haben. Deshalb kann man nicht mehr genau 
sagen, welches von den n Elementen DAS jüngste Element ist (wäre 
hinreichend).

Deshalb ist AGE kein echter LRU-Algorithmus. Ist auch unsinnig sowas zu 
implementieren, da sich der Aufwand i.A. nicht rechnet.

Würde man jedes mal wirklich sortieren, dann wäre durch die Position der 
eindeutige Zugriff bestimmt, das wäre LRU, aber dann braucht man kein 
Age.

Aus diesem Grund wählt man gerne den NFU (Not Frequently Used), 
basierend auf dem Alter, welcher KEIN LRU-Algorithmus sondern eine 
eigene Klasse darstellt.

[Ano N. (oorim)]

Ah, also wenn ich es löse wie jetzt - immer das neueste oben drauf, 
alles andere eins runter rutschen- wäre es LRU aber ineffizient. Führe 
ich eine Alters-Variable ein ist es NFU und es ist nicht atomar welcher 
Eintrag nun wirklich der älteste/wenigsten benutzte ist.

Dann frag ich mich nun aber zwei Dinge:
- Macht das Sinn was ich da zauber?
- Warum steht im Internet bei vielen Artikeln dabei das bei LRU eine Age 
Variable standard ist?

Grüeß

[Andreas H. (andreas_h16)]

>Ich bin derzeit dabei einen Cache zusammenzufrickeln.
>- Macht das Sinn was ich da zauber?
Frickeln oder zaubern, entscheide Dich mal ...


>- Warum steht im Internet bei vielen Artikeln dabei das bei LRU eine
>Age Variable standard ist?
Entweder haben die Autoren der Artikel schlecht plagiert, wörtlich 
plagieren führt immer zu besseren Noten, oder die Artikel sprechen von 
einem modifizierten NFU-Algorithmus, der einem LRU praktisch nahekommt.

Beim modifizierten NFU wird nicht nur das Alter des Eintrags 
gespeichert, sondern es werden auch die Zeitpunkte der letzten Zugriffe 
gewichtet. Kann recht einfach Schiebeoperatoren auf Age realisiert 
werden.

Andererseits könnte Age beim echten LRU auch nicht wirklich das 
zeitliche Alter, sondern die Position in der Zugriffsreihen beinhalten. 
Da wäre der Variablenname aber misleading.

Ich tippe aber eher auf das schlechte Plagiat.

[Ano N. (oorim)]

Du meinst ads schlechte Guttenberg ;)

Frickeln meinte ich weil ichs eben schnell Rapid Prototyping mäßig mit 
wenig Design im VG gebaut habe
Zaubern mein ich im gleichen Sinn^^