STL-Container Auswahl (Transaktionen + Zugriff über ID)

Roger Wilco

Hallo zusammen,

ich möchte Transaktionen zusammen mit einer eindeutigen ID in einen Container ablegen. Dabei soll der Zugriff über die ID erfolgen. Die ID soll fortlaufend vergeben werden. Bei einem Überlauf soll dann bei Null beginnend die nächste freie ID vergeben werden. Die Transaktionen werden zwischenzeitlich gelöscht, i.d.R. nach dem FIFO-Prinzip, aber das ist nicht sicher gestellt. Somit können Lücken entstehen.

Ist ein std::map<uint16_t, Transaction*> dafür geeignet?

Wäre ein paralleler std::set<uint16_t> + std::set<uint16_t>::iterator nextId sinnvoll, um die verfügbaren IDs vorzuhalten?

Roger Wilco

Folgendes habe ich mir gedacht:

#include <memory>
#include <map>
#include <cassert>

namespace
{
    const size_t MAX_UINT16 = 65535;
}

class TransactionBase {...};
typedef std::tr1::shared_ptr<TransactionBase> TransactionPtr;

class TransactionMap
{
    public:
        TransactionMap()
            : m_transactions()
            , m_lastId(0)
        {
            //Dummy-Eintrag um ID=0 zu sperren
            struct Dummy : public TransactionBase{};
            m_transactions[0] = TransactionPtr(new Dummy()); 
        }
    public:
        uint16_t Add(TransactionPtr transaction) //Transaktion hinzufügen
        {
            if(m_transactions.size() >= MAX_UINT16) return 0; //voll!

            // von der letzten ID ausgehend, durchsuchen wir die Map
            // nach dem ersten freien Eintrag
            uint16_t id = m_lastId;
            while(m_transactions[++id]){ assert(id != m_lastId); }
            m_transactions[id] = transaction;
            m_lastId = id;
            return id;
        }
    private:
        std::map<uint16_t, TransactionPtr> m_transactions;
        uint16_t m_lastId; // die zuletzt vergebene ID
};

Macht das Sinn? Würde ein paralleles std::set<uint16_t> Eurer Meinung nach sinnvoll sein? Würdet Ihr einen anderen Ansatz wählen?

Und ist es überhaupt zulässig/vertretbar mit dem gewollten/bewussten Überlauf bei unsigned int zu arbeiten?

while(m_transactions[++id]){ assert(id != m_lastId); }

rean

Müssen die IDs fortlaufend sein? Sobald es zu einem Überlauf kommt kann eine später eingetragene Transaktion ja ohnehin eine niedrigere ID bekommen.

Roger Wilco

Hallo rean,

die Transaktions-ID wird als 16-Bit Integer (unsigned) gespeichert. Damit kann Sie maximal den Wert 65535 annehmen. Sobald diese ID vergeben wurde soll wieder auf 1 zurück gesprungen werden. Ist die 1 noch vergeben, dann soll die nächst höhere freie ID vergeben werden. Daher arbeite ich in meinem Beispiel auch gezielt mit dem Überlauf der Laufvariablen id . Das funktioniert auch, nur frage ich mich ob das vom Standard auch garantiert ist:

uint16_t i = 65535;
++i; i == 0 ?

Die 0 soll als "Keine weiteren Transaktionen zur Zeit möglich!" reserviert werden. Ich denke das ist hier besser als eine Exception, da es zwar unwahrscheinlich ist, aber dennoch logisch möglich ist.

Es besteht aber auch grundsätzlich die Frage, ob das Konstrukt von mir sinnvoll ist.

volkard

Wieviele Transaktionen gleichzeitig sind maximal zu erwarten? Ich nehme an, 65536.

Der AVL-Baum unter der set macht mir da keinen Spaß, der hat bei vollem Tiefe 16, und 32 Bytes pro Knoten sind 2MB.

Eine Hashtable käme mit ca 160k aus und wäre schneller.

Ein Bitfeld mit 8k. Klingt lecker für mich. Geschwindigkeit ist auch kein Problem, weil man auf einem 64-Bitter in 64-er Schritten durchrasen kann mit einer kleinen Schleife, die nur wenige Takte braucht, wenige tausend Takte, wenn sie voll ist. Wenn sie wie praktisch immer recht leer ist, greift ja die Inkrementier-Heuristik und alles ist sauschnell.

Ich würde die 0 nicht überladen, sondern versuchen, sie als ID zulassen. Vielleicht ein pair<bool,uint16_t> zurückgeben. Na, eigentlich doch die Exception, denn die ist schon so unwahrscheilich, wie daß die Platte im Betrieb abkackt.

volkard

Roger Wilco schrieb:

nur frage ich mich ob das vom Standard auch garantiert ist:
uint16_t i = 65535;
++i; i == 0 ?

Ich vermute nicht, daß das garantiert ist. Aber daß Deine Maschine es anders handhabt, ist so tierisch unwahrscheinlich, daß ich es darauf anlegen würde.
Kanns ja ins Makefile einen test reinhauen, ob es auf der Maschine so ist.

Oder ein static_assert(uint16_t(uint16_t(65536)+uint16_t(1))==uint16_t(0),"strange machine error, please email roger.wilco@gmx.de"); reinhauen, ist vielleicht besser, das müßte die Zielmaschine befragen statt der Makemaschine.

Roger Wilco

Hallo volkard,

volkard schrieb:

Wieviele Transaktionen gleichzeitig sind maximal zu erwarten?

Die Spezifikation gibt da nichts vor, nur dass die ID 16Bit groß ist. Somit wären 65535 gleichzeitige Transaktionen theoretisch möglich. In der Praxis wäre das mit sehr sehr hoher Wahrscheinlichkeit ein Indiz für einen Fehler.

Eine Exception wäre mir da auch lieber.

volkard schrieb:

Ein Bitfeld mit 8k. Klingt lecker für mich.

Denkst Du da an std::bitset bzw. std::vector<bool> ? Die std::map als Container für die Transaktionen wäre OK?

volkard schrieb:

Roger Wilco schrieb:
nur frage ich mich ob das vom Standard auch garantiert ist:
uint16_t i = 65535;
++i; i == 0 ?
Ich vermute nicht, daß das garantiert ist.

Es scheint doch garantiert zu sein:

C++ Standard 3.9.1/4 schrieb:

Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2ⁿ where n is the number of bits in the
value representation of that particular size of integer. ⁴⁶⁾

⁴⁶⁾ This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is
reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.

volkard

Roger Wilco schrieb:

volkard schrieb:

Ein Bitfeld mit 8k. Klingt lecker für mich.

Denkst Du da an std::bitset bzw. std::vector<bool> ?

bitset, denn die Größe ist compilezeitkonstant. Aber eigentlich eine eigene Implementierung, die eine besonders schnelle findNextBitTrue hat.

Roger Wilco schrieb:

Die std::map als Container für die Transaktionen wäre OK?

Es ist die naheliegende Lösung, aber eine unordered_map klingt auch nicht so schlecht. Zumal sie klein bleibt, außer in krankhaften Fällen. Die erste Hashfunktion wäre ID*40503 oder mal ganz trocken ID*1. Man könnte sich überlegen, dann keine bitset davorzuschalten.

Ich glaube, ich würde was eigenes bauen, zweistufiger Baum oder Hashtable.

Oder ich würde länger üder die ID-Vergabe nachdenken. Vielleicht reicht es, den Schlüsselraum in 128 große Fenster zu zerlegen und sich pro Fenster sich nur die Anzahl der belegten IDs merken und immer, wenn das aktuelle Fenster nichst mehr hat, das nächste komplett freie Fenster zu nehmen, und daraus 128 ID sprudeln zu lassen. Und nur wenn es kein komplett freies Fenster gibt, zurückfallen auf Einzelprüfung auf der (unordered_)set. Das wäre schnell, aber die IDs würden nicht mehr maximalen zeitlichen Abstand haben, bevor sie erneut vergeben werden.

Vielleicht reicht es, den Schlüsselraum in 128 große Fenster zu zerlegen und sich pro Fenster sich nur die Anzahl der belegten IDs merken und normal die freie ID in der (unordered_)set suchen, aber immer, wenn das aktuelle Fenster keine freie ID mehr hat, das nächste nicht komplett volle Fenster suchen. Das kostet wiedermal normalerweise ungefähr nichts, aber beschränkt bei sehr vielen vergebenen IDs die Suche. Nicht mehr um 60000 set-Suchen, sondern nur noch maximal 512 Tests, ob das Fenster voll ist und max 128 set-Suchen.

Das gibt ja schier endlose Möglichkeiten. Mir scheint, nur eines ist gewiß: Wenn der Code fertig ist, fällt einem eine noch hübschere Lösung ein.

rean

Ich hab hier noch eine auf bitset basierende Lösung für sowas rumfliegen:

#include <limits>

template< typename IDType, typename StorageType = unsigned int >
class idmap
{
private:	
	const IDType MinID;

	const StorageType MaxStorageValue;

	static const size_t MaxIDCount = ( 1 << ( CHAR_BIT * sizeof( IDType ) ) );
	static const size_t Bitsperword = (size_t)( CHAR_BIT * sizeof( StorageType ) );
	static const size_t Words = (size_t)( ( MaxIDCount - 1 ) / Bitsperword );

	#define BIT_INDEX( pos ) ( pos & ( Bitsperword - 1 ) ) //Faster modulo
	#define WORD_INDEX( pos ) ( pos >> ( sizeof( StorageType ) + 1 ) ) //Faster divide

public:

	idmap( IDType startID = IDType() ) :
	  MinID( std::numeric_limits< typename IDType >::min() ),
	  MaxStorageValue( std::numeric_limits< typename StorageType >::max() ),
	  m_idLastID( startID )
	{
		setAll( 0 );
	}

	//Test if the given ID is already used
	bool test( IDType id ) const
	{
		size_t pos = id - MinID;

		return ( ( Array[ WORD_INDEX( pos ) ] & ( (StorageType)1 << BIT_INDEX( pos ) ) ) != 0 );
	}

	//Returns the next free ID, based on the ID that was
	//returned by the last call to any of the next-overloads
	IDType next( bool &full )
	{
		//next overrides m_idLastID
		IDType tmp = m_idLastID;

		next( m_idLastID );

		full = ( tmp == m_idLastID );

		return m_idLastID;
	}

	//Search for the next free ID, starting from the given one.
	//Will return the given ID if there are no more free IDs.
	IDType next( IDType id )
	{
		const size_t pos = id - MinID;

		//Faster modulo and divide
		const int bitPos = BIT_INDEX( pos );
		const int wordPos = WORD_INDEX( pos );

		//Search all remaining bits of the word of the given ID
		int ret = setIDForward( Array[ wordPos ], bitPos + 1 );

		if( ret != -1 ){ return ( m_idLastID = id + ret - bitPos ); }

		//No free ID found in word of given ID
		//search from current word to the end
		ret = setWordIDForward( wordPos + 1, Words + 1 );

		if( ret != - 1 ){ return ( m_idLastID = ret + MinID ); }

		//No free ID found, round wrap search
		ret = setWordIDForward( 0, wordPos );

		if( ret != -1 ){ return ( m_idLastID = ret + MinID ); }

		//No free ID found, try the word of the given ID
		ret = setIDForward( Array[ wordPos ], 0, bitPos );

		if( ret != -1 ){ return ( m_idLastID = id + ret - bitPos ); }

		//No free ID found, return the given ID
		return ( m_idLastID = id );
	}

	//Sets or resets the given ID
	void set( IDType id, bool val = true )
	{
		size_t pos = id - MinID;

		if( val )
			Array[ WORD_INDEX( pos ) ] |= ( (StorageType)1 << BIT_INDEX( pos ) );
		else
			Array[ WORD_INDEX( pos ) ] &= ~( (StorageType)1 << BIT_INDEX( pos ) );

		return (*this);
	}

	//Sets all IDs
	void set()
	{
		setAll( (StorageType)~0 );
	}

	//Resets all IDs
	void reset()
	{
		setAll( 0 );
	}

	//Returns true if there are no more free IDs
	bool full()
	{
		for( int i = Words; i >= 0; --i )
		{
			if( Array[ i ] != MaxStorageValue ){ return false; }
		}
		return true;
	}

	//Returns true if there are set IDs
	bool empty()
	{
		for( int i = Words; i >= 0; --i )
		{
			if( Array[ i ] != 0 ){ return false; }
		}
		return true;
	}

private:

	//Search the given word from bitPos to maxPos-1 for a free ID
	int setIDForward( StorageType &word, int bitPos, int maxPos = Bitsperword )
	{
		StorageType testBit = (StorageType)1 << bitPos;

		for( ; bitPos < maxPos; ++bitPos )
		{
			if( ( word & testBit ) == 0 )
			{
				word |= testBit;

				return bitPos;
			}

			testBit <<= 1;
		}

		return -1;
	}

	//Search the array from begin to end-1 for a free ID
	int setWordIDForward( int begin, int end )
	{
		int ret;

		for( int i = begin; i < end; ++i )
		{
			//word is empty
			if( Array[ i ] == 0 )
			{
				//set LSB
				Array[ i ] = 1;

				//Faster multiplication, same as i * Bitsperword
				return ( i << ( sizeof( StorageType ) + 1 ) );
			}
			//word is partially full
			else if( Array[ i ] != MaxStorageValue )
			{
				ret = setIDForward( Array[ i ], 0 );

				if( ret != -1 )
				{
					//Faster multiplication, same as i * Bitsperword
					return ( i << ( sizeof( StorageType ) + 1 ) ) + ret;
				}
			}
		}
		return -1;
	}

	//Sets all words to the given value.
	void setAll( StorageType val )
	{
		for( int i = Words; i >= 0; --i )
		{
			Array[ i ] = val;
		}
	}

private:

	//The last Id that was returned by one of the next-overloads
	IDType m_idLastID;

	//The array of words
	StorageType Array[ Words + 1 ];
};

Kann an der einen oder anderen Stelle noch minimal optimiert werden, läuft aber schon ganz flott.
Eine Erweiterung um eigene Typen zu speichern überlasse ich dem geneigten Entwickler

Roger Wilco

Vielen Dank Euch beiden!

Ich werde mir dazu erstmal ein paar Gedanken machen und mich mehr in die Container einarbeiten. map , unordered_map , set etc. sind für mich noch recht neu. Gerade volkards Gedankengänge überfordern meine dann doch noch ein wenig...

Ich werde ausgehend von der reinen map ein paar Tests machen. Ich werde auch eine Liste in Erwägung ziehen, da im Normalfall das Einfügen und Löschen der Transaktionen nach dem FIFO-Prinzip erfolgt. Im Regelfall wird auch immer die nächste ID verfügbar sein.