{"id":479,"date":"2009-06-14T12:51:48","date_gmt":"2009-06-14T10:51:48","guid":{"rendered":"http:\/\/blog.m-ri.de\/?p=479"},"modified":"2009-06-22T10:38:22","modified_gmt":"2009-06-22T08:38:22","slug":"die-hashkey-implementierung-in-der-mfc-in-vc-2005-und-vc-2008","status":"publish","type":"post","link":"http:\/\/blog.m-ri.de\/index.php\/2009\/06\/14\/die-hashkey-implementierung-in-der-mfc-in-vc-2005-und-vc-2008\/","title":{"rendered":"Die HashKey Implementierung in der MFC in VC-2005 und VC-2008"},"content":{"rendered":"

Die Maps in der MFC werden ja auch zum Teil gerne verwendet. Auch wenn viele Programmierer eher auf die std::map<\/em> bzw. std::hash_map <\/em>verwenden.<\/p>\n

Zwei interne Dinge sind jedoch vielen Entwicklern nicht klar.<\/p>\n

    \n
  1. Die Standard-Maps der MFC werden mit 17 Hash-Buckets erzeugt. Man sollte sich also \u00fcber die Anzahl der Elemente klar werden, die gespeichert werden sollen.
    \nBei gro\u00dfen Datenmengen sollte man evtl. dar\u00fcber nachdenken, die Anzahl der Buckets zu erh\u00f6hen.<\/li>\n
  2. Ist die Hash Funktion zu beachten, die hier verwendet wird. Denn deren Effektivit\u00e4t entscheidet ja, wie die Eintr\u00e4ge auf die Buckets verteilt werden.<\/li>\n<\/ol>\n

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

    template<class ARG_KEY>\r\nAFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)\r\n{\r\n\u00a0\/\/ default identity hash - works for most primitive values\r\n\u00a0return (DWORD)(((DWORD_PTR)key)>>4);\r\n}<\/pre>\n
    Das erstaunliche ist f\u00fcr mich, dass hier die untersten 4 Bits einfach abgeschnitten werden. F\u00fcr mich h\u00e4tte f\u00fcr Handles, Zeiger und Integer Werte einfach ein cast gelangt.<\/p>\n
    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.<\/p>\n
    Der Nachteil ist offensichtlich. Man nutzt das Datenrauschen auf den untersten 4 Bits nicht.
    \nDas 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\u00fctzliche „zuf\u00e4llige“ Informationen nicht genutzt. Dadurch werden mehr Kollisionen in Kauf genommen als notwendig w\u00e4ren.<\/p>\n
    Ich m\u00f6chte nicht unerw\u00e4hnt lassen, dass die MFC <\/em>Maps wirklich eine Berechtigung haben, weil sie grunds\u00e4tzlich einen Pool-Allocator verwenden. H\u00e4ufige Allokationen und L\u00f6schungen werden weitaus schneller behandelt, als durch die std::map<\/em>, oder std::hash_map <\/em>mit normalen Allocator.<\/p>\n
    Ich habe diesen Bug (oder miese Verhalten) bereits in der Beta f\u00fcr VC-2008 gemeldet. Es wurde aber nicht mehr ge\u00e4ndert. Nun habe ich es an die Produktgruppe erneut\u00a0 f\u00fcr VC-10 eingereicht.
    \nhttps:\/\/connect.microsoft.com\/VisualStudio\/feedback\/ViewFeedback.aspx?FeedbackID=100772<\/a>
    \nNachtrag 22.06.2009: Da der Bug von Microsoft nicht neu ge\u00f6ffnet wird habe ich einen neuen f\u00fcr VS-2010 Beta 1 angelegt.
    \n<\/em>    https:\/\/connect.microsoft.com\/VisualStudio\/feedback\/ViewFeedback.aspx?FeedbackID=468860<\/a>
    \nWer Lust hat, der kann ja abstimmen.<\/p>\n
    BTW: Die HaskKey <\/em>Funktion in afxtempl.h<\/em> ist f\u00fcr andere Maps (z.B. CMapPtrToPtr<\/em>) direkt in der Klasse definiert. Dieses Template wird nur vom CMap<\/em>-Template verwendet.<\/p>\n","protected":false},"excerpt":{"rendered":"
    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. Die Standard-Maps der MFC werden mit 17 Hash-Buckets erzeugt. Man sollte sich also \u00fcber die Anzahl der Elemente klar werden, die gespeichert werden … \u201eDie HashKey Implementierung in der MFC in VC-2005 und VC-2008\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4,3,27,172],"tags":[99,352,36,44,171],"class_list":["post-479","post","type-post","status-publish","format-standard","hentry","category-mfc","category-programmieren","category-vs2008","category-vs2010","tag-bug","tag-mfc","tag-vs-2005","tag-vs-2008","tag-vs-2010"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts\/479","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/comments?post=479"}],"version-history":[{"count":1,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts\/479\/revisions"}],"predecessor-version":[{"id":483,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts\/479\/revisions\/483"}],"wp:attachment":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/media?parent=479"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/categories?post=479"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/tags?post=479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}