Kategorie: Programmieren

Die Maps in der MFC werden ja auch zum Teil gerne verwendet. Auch wenn viele Programmierer eher auf die std::map bzw. std::hash_map verwenden.

Zwei interne Dinge sind jedoch vielen Entwicklern nicht klar.

1. Die Standard-Maps der MFC werden mit 17 Hash-Buckets erzeugt. Man sollte sich also über die Anzahl der Elemente klar werden, die gespeichert werden sollen.
   Bei großen Datenmengen sollte man evtl. darüber nachdenken, die Anzahl der Buckets zu erhöhen.
2. Ist die Hash Funktion zu beachten, die hier verwendet wird. Denn deren Effektivität entscheidet ja, wie die Einträge auf die Buckets verteilt werden.

Zu diesem zweiten Punkt macht man eine erstaunliche Entdeckung, wenn man sich ansieht, was Microsoft für eine Funktion vorgesehen hat um den Hask-Key zu erzeugen. Diese Funktion ist in der MFC für primitive Werte vordefiniert, als primitive Werte sehe ich alle numerischen Werte, Zeiger und Handle an.
Man findet eine Implementierung als Template-Funktion in afxtempl.h:

template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
 // default identity hash - works for most primitive values
 return (DWORD)(((DWORD_PTR)key)>>4);
}

Das erstaunliche ist für mich, dass hier die untersten 4 Bits einfach abgeschnitten werden. Für mich hätte für Handles, Zeiger und Integer Werte einfach ein cast gelangt.

Nehmen wir jetzt mal an, wir haben eine einfache Datenmenge, die die Integer 1-100 auf eine Struktur abbilden. Man wird die erstaunliche Entdeckung machen, dass alle Werte nur in den Buckets 0-6 abgespeichert werden. Die Buckets 7 bis 16 werden nicht verwendet.

Der Nachteil ist offensichtlich. Man nutzt das Datenrauschen auf den untersten 4 Bits nicht.
Das macht sich sogar bei Fensterhandles bemerkbar. Bekanntlich sind das immer gerade Werte, aber auch auf den Bits 1-3 finden wir hier Informationen. Auch hier werden nützliche „zufällige“ Informationen nicht genutzt. Dadurch werden mehr Kollisionen in Kauf genommen als notwendig wären.

Ich möchte nicht unerwähnt lassen, dass die MFC Maps wirklich eine Berechtigung haben, weil sie grundsätzlich einen Pool-Allocator verwenden. Häufige Allokationen und Löschungen werden weitaus schneller behandelt, als durch die std::map, oder std::hash_map mit normalen Allocator.

Ich habe diesen Bug (oder miese Verhalten) bereits in der Beta für VC-2008 gemeldet. Es wurde aber nicht mehr geändert. Nun habe ich es an die Produktgruppe erneut  für VC-10 eingereicht.
https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=100772
Nachtrag 22.06.2009: Da der Bug von Microsoft nicht neu geöffnet wird habe ich einen neuen für VS-2010 Beta 1 angelegt.
https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=468860
Wer Lust hat, der kann ja abstimmen.

BTW: Die HaskKey Funktion in afxtempl.h ist für andere Maps (z.B. CMapPtrToPtr) direkt in der Klasse definiert. Dieses Template wird nur vom CMap-Template verwendet.