Welche cache-strategie wäre am sinnvollsten? LRU?

[afaiko]

Hallo,

im Prinzip ist mein Programm eine doppelte for-schleife. Die anzahl an iterationen ist durchaus > 100000.
Ich habe einen cache (ein einfaches array aus einer structure) der vom Prinzip her double-vektoren speichert. Bevor ich eine Funktion aufrufe schaue ich ob der zu berechnende double-vektor nicht schon vorher in einer vorigen iteration berechnet wurde. Falls ja extrahiere ich den vector aus dem cache und überspringe die funktion. Falls nicht, berechne ich ihn und speichere ihn. Damit erwarte ich mir geschwindigkeitsvorteil die auch schon bei manchen inputs eintreten. Der cache ist dimensionert auf 10 bis 1000 elemente. Ich habe das frei wählbar über einen input-parameter. Das könnte ich noch anpassen. Prinzipiell arbeite ich mit einer cache-grösse von ca. 100, wobei aber in einem gesamten durchlauf z.B eben 100000 elemente gebraucht werden. D.h es müssen zwangsläufig elemente raus und wieder rein. Ich habe im Moment einen LRU-Mechanismus der immer das älteste element rausschmeißt und an diese position das gerade neue einfügt.

Meine Frage: Kann ich von euch einen Tipp erwarten/bekommen obwoh das ein sehr spezielles Problem ist?
Wenn ja: Ist der LRU-mechansismus eine bessere Wahl? Antworten wie probiers aus sind mir klar - ich tue das auch - es könnte aber auch sein das jemand schon mal ein ähnliches Problem hatte und die goldene Weißheit schon parat hat

Danke euch vielmals

[Th]

Bezieht sich die angegebene Zahl (100000) auf beide Schleifen (je >100) oder pro Schleife?
Und wie prüfst du, ob ein Vektor schon berechnet wurde (ich hoffe mal, nicht linear)?

Wenn du extra einen Cache mit nur wenigen Elementen hast, hast du irgendwelche Speicherprobleme?
Und bist du dann sicher, daß sich der Aufwand für einen Cache lohnt, d.h. wie oft (prozentual) wird ein Wert aus dem Cache genommen, anstatt neu berechnet zu werden? Bezogen auf die Frage zu LRU, kommt es sicherlich darauf an, ob die Input-Daten sehr ähnlich sind, d.h. bezogen auf die Cache-Größe gleiche Daten oft hintereinander auftauchen.

Am besten, du postest mal deinen Code (bzw. als Pseudo-Code).

[crashterpiece]

wie aufwendig ist denn die berechnung der einzelnen werte?? ein paar additionen etc oder doch ne zeitintensive prozedur? ggf würde sich die gesamte cache-idee kippen, wenn die werte einfach brute-force durchgerechnet werden... compiler und cpu können schliesslich auch interne cache-optimierungen durchführen, manchmal ist mehrarbeit schliesslich effektiver

[hustbaer]

Ohne genauere Informationen darüber was hier gecachet werden soll und was man über die Reihenfolge in der die zu cachenden Elemente angefragt werden vermuten kann ... wird dir wohl keiner einen besseren Tip geben können als "probier es halt aus".

LRU funktioniert für die meisten Anwendungen recht gut, allerdings kann es Fälle geben wo anderen Verfahren bessere Resultate bringen.
Wenn ich z.B. weiss dass die Häufigkeit mit der ein Element angefordert wird für die ersten N Elemente ungleich grösser ist als für alle weiteren, dann wird es wohl Sinn machen diese in einen eigenen Bereich im Cache zu stecken der nie "verworfen" wird.

Ich habe im Moment einen LRU-Mechanismus der immer das älteste element rausschmeißt und an diese position das gerade neue einfügt.

Das verstehe ich nicht ganz. Entweder es ist LRU oder es ist nicht LRU.
LRU wäre:
Cache Miss: letztes Element rauswerfen und neues ganz vorne reinstellen.
Cache Hit: gefundenes Element ganz nach vorne reihen.

Alles andere ist IMO kein LRU.

[afaiko]

Bezieht sich die angegebene Zahl (100000) auf beide Schleifen (je >100) oder pro Schleife?

nö schon für beide, gut es kann schon vorkommen dass ich dann z.b mal 200 000 durchläufe habe oder auch nur 50 000.
Also es sind 2 riesige for-schleifen wo intern massig zeug gerechnet wird...aber so von der vorstellung halt.

Und wie prüfst du, ob ein Vektor schon berechnet wurde (ich hoffe mal, nicht linear)?

hmm - wie sonst? gut man könnte ein hashtable aufbauen....falls mein overhead zu groß wird denke ich darüber nach ja.

Wenn du extra einen Cache mit nur wenigen Elementen hast, hast du irgendwelche Speicherprobleme?

nö hab ich eigentlich nicht. Aber ab einer bestimmen grösse wird der overhead zu groß - was das hashtable wohl sinnvoller erscheinen lässt ja.

Und bist du dann sicher, daß sich der Aufwand für einen Cache lohnt, d.h. wie oft (prozentual) wird ein Wert aus dem Cache genommen, anstatt neu berechnet zu werden?

ja sollte sinn machen. Also es hängt natürlich vom input ab aber es kann durchaus vorkommen, dass über 50% aus dem cache gezogen werden.

Bezogen auf die Frage zu LRU, kommt es sicherlich darauf an, ob die Input-Daten sehr ähnlich sind, d.h. bezogen auf die Cache-Größe gleiche Daten oft hintereinander auftauchen.

joa - kann man so sagen. es sind große Matrizen die durchaus oft symmetrisch oder auch tridiagonals-struktur haben. Also eher ja.

wie aufwendig ist denn die berechnung der einzelnen werte?? ein paar additionen etc oder doch ne zeitintensive prozedur?

die habe ich hier schon mal im forum gepostet. im grunde eine iteration über den double-vector um daraus einen möglichst eindeutigen schlüssel zu generieren - siehe code unten

ggf würde sich die gesamte cache-idee kippen, wenn die werte einfach brute-force durchgerechnet werden...

das teste ich ja gerade ausgiebig - habe eine variante ohne cache und eine mit cache - denke aber das der cache durchaus was bringen sollte....

Ohne genauere Informationen darüber was hier gecachet werden soll und was man über die Reihenfolge in der die zu cachenden Elemente angefragt werden vermuten kann ... wird dir wohl keiner einen besseren Tip geben können als "probier es halt aus".

ja das dachte ich mir schon irgendwie - aber man stösst dann doch wieder auf neue wege wenn jemand senf dazu gibt

LRU funktioniert für die meisten Anwendungen recht gut, allerdings kann es Fälle geben wo anderen Verfahren bessere Resultate bringen.
Wenn ich z.B. weiss dass die Häufigkeit mit der ein Element angefordert wird für die ersten N Elemente ungleich grösser ist als für alle weiteren, dann wird es wohl Sinn machen diese in einen eigenen Bereich im Cache zu stecken der nie "verworfen" wird.

interessant ...

Das verstehe ich nicht ganz. Entweder es ist LRU oder es ist nicht LRU.
LRU wäre:
Cache Miss: letztes Element rauswerfen und neues ganz vorne reinstellen.
Cache Hit: gefundenes Element ganz nach vorne reihen.

Alles andere ist IMO kein LRU.

puh...da hab ich wohl was falsch verstanden. Ich dachte LRU ist halt last recently used, das älteste wird rausgehauen an seiner stelle und dann das neue rein.
wenn ihc in einem array ein elemente vorne einfügen wollen würde obwohl es nicht das älteste ist, müsste ich ja alle elente vor der zu löschenden stelle um eins nach hinten schieben - ist doch unsinnig oder ?
dauert dann doch noch länger oder net?

UND ich weiß dass ich die stl benutzen hätte können mit std::vector oder dergleichen...

template <class T>
struct CACHE_DATA
{
    T* vec1;
    T* vec2;
    T* vec3; 
};

typedef unsigned int U_Int32;
typedef U_Int32 Key;

template <class T>
Cache<T>::Cache(const int dimension)
{
    m_dimension = dimension;
    m_cache = new std::pair<Key, CACHE_DATA<T> >[dimension];

    m_priority = new int[dimension];
    memset(m_priority, 0, dimension * sizeof(int));

    m_cache_key = 0;
}

template <class T>
Cache<T>::~Cache()
{
	for(int i = 0; i < m_dimension; i++)
		Delete_Cache_Element(i);
	delete [] m_cache;	
	delete [] m_priority;
}

template <class T>	void 
Cache<T>::Delete_Cache_Element(int idx)
{
	std::pair<Key, CACHE_DATA<T> > 	
					cp;

    struct 
	CACHE_DATA<T>	cd;

    cp = m_cache[idx];
    cd = cp.second;

	if (cd.vec1)	delete [] cd.vec1;
	if (cd.vec2)			delete [] cd.vec2;
 	if (cd.vec3)		delete [] cd.vec3;
}

template <class T>	void 
Cache<T>::Insert_Cache_Data_LRU(U_Int32 key, 
                               T* vec1, 
                               T* vec2,
                               T* vec3)
 {

    int insert_idx 		= 
			GetMaxIdx_UpdatePriority();

    Delete_Cache_Element(insert_idx); 

    struct CACHE_DATA<T> cd;
    cd.vec1 		= vec1;
    cd.vec2 				= vec2;
    cd.vec3 			= vec3;

	m_cache[insert_idx] = 
			std::pair<Key, CACHE_DATA<T> >(key, cd); 
}

template <class T>	int 
Cache<T>::GetMaxIdx_UpdatePriority()
{    
    int max_idx = 0;
    int max_val = m_priority[max_idx];

    for(int idx = 1; idx < m_dimension; idx++)
    {
        if(m_priority[idx] > max_val)
        {
            max_val = m_priority[idx];
            m_priority[max_idx]++;
            max_idx = idx; 
        }
        else
            m_priority[idx]++;   
    }
    m_priority[max_idx] = 0;

    return max_idx;
}

template <class T>	void 
Cache<T>::Update_LRU_Priorities(const int idx)
{
    for(int i = 0; i < m_dimension; i++)
        m_priority[i]++;
    m_priority[idx] = 0;
}

template <class T>	int 
Cache<T>::In_Cache(const U_Int32 pattern_key)
{   
	std::pair<Key, CACHE_DATA<T> > cp;
	for(int i = 0; i < m_dimension; i++)
    {
        cp = m_cache[i];
        if(pattern_key == cp.first)
			return i;
    } 
    return -1;
}

template <class T>	std::pair<Key, CACHE_DATA<T> >
Cache<T>::Get_Cache_Element(const int idx)
{
	std::pair<Key, CACHE_DATA<T> > cp 
			= m_cache[idx];
    return cp;
}

template <class T>	inline U_Int32 
Cache<T>::Hash_Double(double x)
{ 
	U_Int32 p[2];
	memcpy( p, &x, sizeof p );
	return p[0] ^ p[1];
}

template <>	U_Int32 
Cache<double>::Compute_Key(	const double* vec, 
							size_t size) const
{                    
	U_Int32 ret = 0;
	U_Int32 mix = Hash_Double(0.13);
	while(size--)
	{
		ret = (ret * 31) + mix + Hash_Double(*vec);
		vec++;
	} 
	return ret;
}

[thordk]

LRU heisst least recently used und genau das soll es auch bedeuten. die strategie ist, die daten aus dem cache zu kicken, auf die am seltensten zugegriffen wird. das ganze als warteschlange zu betrachten ist nur eine mögliche implementierung.

[Th]

Du schreibst, du hast eine große Anzahl von Daten (> 100000), die Berechnung der einzelnen Daten ist sehr aufwändig und daher benutzt du einen Cache, aber du hast keine Speicherprobleme.
Warum speicherst du dann nicht einfach ALLE berechneten Daten ab und fügst die in eine Hash-Map (bzw. zumindestens eine normale Map mit logaritmischem Zugriff) ein (den Key dafür hast du ja schon berechnet).
Oder wenn dir dann irgendwann der Speicher dafür zu knapp wird, dann mußt du halt die an wenigsten benutzen Daten wieder löschen (d.h. du mußt dir noch merken, wie oft jedes Datenelement benutzt wurde).

[afaiko]

Danke für die Beiträge.

Du schreibst, du hast eine große Anzahl von Daten (> 100000), die Berechnung der einzelnen Daten ist sehr aufwändig und daher benutzt du einen Cache, aber du hast keine Speicherprobleme.
Warum speicherst du dann nicht einfach ALLE berechneten Daten ab und fügst die in eine Hash-Map (bzw. zumindestens eine normale Map mit logaritmischem Zugriff) ein (den Key dafür hast du ja schon berechnet).
Oder wenn dir dann irgendwann der Speicher dafür zu knapp wird, dann mußt du halt die an wenigsten benutzen Daten wieder löschen (d.h. du mußt dir noch merken, wie oft jedes Datenelement benutzt wurde).

völlig korrekt der Vorschlag ja. Ich könnte ja die Hash-map von der Grösse her auch beschränken oder?

Ich bin im Moment noch am messen wieviel Overhead die Suche meiner Daten braucht.
SOweit ich aber weiß gibt es eine Hash-Map als fertige Datenstruktur unter C++ nicht oder? Lediglich die von Dir vorgeschlagene map.
In diesem Sinne müsste ich mir auch keine Gedanken über die Cache-Strategie (also LRU) machen - die fiele durch die map weg ja.

Für weiter Anregungen bin ich gerne offen - Danke

[hustbaer]

thordk schrieb:

LRU heisst least recently used und genau das soll es auch bedeuten. die strategie ist, die daten aus dem cache zu kicken, auf die am seltensten zugegriffen wird. das ganze als warteschlange zu betrachten ist nur eine mögliche implementierung.

Falsch.
Last Recently Used (aka. Least Recently Used) bedeutet "am längsten nicht benützt" und nicht "am seltensten". Das ist ein grosser Unterschied.

Die Implementierung über eine Warteschlange ist nur eine Möglichkeit es zu implementieren, aber jede LRU Implementierung muss das gleiche Verhalten zeigen (was das "welches Element fliegt wann raus" angeht) wie die Version mit der Warteschlange, sonst ist es kein LRU mehr.

[afaiko]

Hat das das von mir überhaupt einen Namen?
Ich schmeiße zwar das älteste raus, reihe es aber vorne nicht ein....

sollte ich dann doch eine warteschlange bauen anstatt eines normalen arrays um die verschiebung der elemente zu realisieren sozusagen?

[thordk]

hustbaer schrieb:

Last Recently Used (aka. Least Recently Used) bedeutet "am längsten nicht benützt" und nicht "am seltensten".

du solltest den fokus auf least setzen, nicht recently. daten, auf die "am wenigsten" zugegriffen wird, nicht "zuletzt".

[finix]

thordk schrieb:

hustbaer schrieb:

Last Recently Used (aka. Least Recently Used) bedeutet "am längsten nicht benützt" und nicht "am seltensten".

du solltest den fokus auf least setzen, nicht recently. daten, auf die "am wenigsten" zugegriffen wird, nicht "zuletzt".

Und du solltest deine Englisch- und/oder Fachkenntnisse vertiefen.

[hustbaer]

@thordk:
Lies es doch nach wenn du mir nicht glaubst.

Was du meinst ist LFU: Least Frequently Used.

[hustbaer]

afaiko schrieb:

Hat das das von mir überhaupt einen Namen?
Ich schmeiße zwar das älteste raus, reihe es aber vorne nicht ein....

sollte ich dann doch eine warteschlange bauen anstatt eines normalen arrays um die verschiebung der elemente zu realisieren sozusagen?

Äh.
Wie findest du denn das älteste Element?
Wenn du keine Queue verwendest müsstest du ja zu jedem Element irgendwie ein "Alter" mitspeichern. Und jedesmal wenn du ein Element rauswirfst das "älteste" suchen.

Wenn du das so machst dann ist es LRU. Wie es implementiert ist ist ja wie gesagt egal, wichtig ist nur wann welches Element rausgeworfen wird, also das "beobachtbare Verhalten" wenn man es so nennen will.

[afaiko]

h.
Wie findest du denn das älteste Element?
Wenn du keine Queue verwendest müsstest du ja zu jedem Element irgendwie ein "Alter" mitspeichern. Und jedesmal wenn du ein Element rauswirfst das "älteste" suchen.

Jo so ist es. Ich habe ein zusätzliches array wo ich prioritäten habe. Bei jedem insert an der stelle wird die priorität auf 0 gesetzt. Bei jeder suche nach dem ältesten element , wird jede priorität gleichzeitig um 1 erhöht.
Das ist natürlich linearer aufwand ja. Aber so kann ich zumindest die ältesten bestimmen.

Ich glaube ich probiere mal ein hash-table. Weiß jemand zufällig wie ich an ein vordefiniertes rankomme? Weil unter C++ gibts so was ja net in der std oder?

Danke

[afaiko]

ich sehe gerade dass es sowas wie ne <ext/hash_map> gibt.
Kann ich das hash-table von der grösse her beschränken? Ginge das?