User Tag List

Page 1 of 2 1 2 LastLast
Results 1 to 10 of 20

Thread: This is how we roll

  1. #1
    Developer ZC Developer
    Gleeok's Avatar
    Join Date
    Apr 2007
    Posts
    4,623
    Mentioned
    211 Post(s)
    Tagged
    10 Thread(s)
    vBActivity - Stats
    Points
    12,171
    Level
    32
    vBActivity - Bars
    Lv. Percent
    39.83%
    Daily Activity
    0%
    Weekly Activity
    5.3%
    Monthly Activity
    38.59%

    This is how we roll

    (Normally I'd just skip threads like this and the last one, but I'm trying to post here more so... yeah ... Worked on it a bit yesterday and today. Put in a few missing thingies and am currently debating whether to use a 3D perspective or orthographic camera for map areas/everything else.. I'm on the fence, but for now it is a 2D camera. Anyway, back on topic...)

    As you may or may not know I pretty much hate the c++ standard template library--I think it's bloated junk. So I just "roll my own" *whatever* whenever I need something. They are faster and I can change anything I want about it pretty much whenever I feel like it and know exactly what it does under the hood, so I see it as a win win. It also keeps compile times down and exe sizes smaller yada yada. Point is I am completely anti-pattern guy and definitely in the minority on this issue. Truth be told I don't actually even use c++11 or c++14. I think the language is getting too ugly and bloated, and there's no features I really would even use in it(except maybe typed enums or usings). It's like the hero Gotham wanted, but not the one it needs right now. (shakes hands at clouds)

    So I roll my own stuff occasionally and finally got around to putting in a hash table. Before I was kind of just using sorted arrays and faking it using binary searches.
    For other projects if I needed a hash map I actually used to use rde::hash_map: http://msinilo.pl/blog/?p=675
    Google hash maps are also pretty good: http://code.google.com/p/sparsehash/

    Truth is that making your own hash map is kind of stupid, since there's tons of good ones available, and it's easy to screw up a minor detail here or there thus giving you a real headache to debug down the road. Yes, I am definitely a dumb-ass sometimes. heh. ..But! Just using a google thingy is no fun now, is it?!

    The use case is I wanted open addressing (aka; raw array) and linear probing (so entries would be preferably in a single cache-line on lookups), and insert and lookup times to be as fast as possible, and for removals I envision two things: 1) erases are not speed important, and 2) erasures may be skipped entirely, depending on use, and just cleared instead. Another detail of open hashtables is performance can rapidly deteriorate due to having to mark deleted entries as 'REMOVED' to handle collisions properly, and eventually they can become just like linear array lookups unless it's rehashed. Another problem is when the load capacity of a hash map becomes too great (usually after 70% load or so) performance can also degrade because of key clustering, so you have to over allocate the memory you actually need. This is a real killer, and may be one reason why most hash maps use chaining and linked-lists approach, such as the stl, for example, which gives shitty performance and shitty memory access patterns... And that's why I always just put it off for a rainy day.

    However, this week I was thinking about using a hash map for something, and then it just hit me: You don't need to mark nodes as deleted if you are just storing POD in them, you can just 'uncollide' them! When removing an entry you can look ahead until you find an unused slot and fix hash collisions along the way, thus eliminating the need to have handle special cases when looking up data. So I called it reverse colliding removals. I had just invented a better hashtable! yayzors. ...or so I thought. Turns out they used that concept in the rust programming language library. It's called a 'backward shift deletion'. Of course I didn't know that until after I had written it and decided to look it up. Hahaha..

    It was still a fun exercise to do though. So whatever. And on the plus side it has very good performance. So much so that it probably is a good basis for comparison for serious implementations.


    I also made a unit test and benchmark. You guys wanna see it here it goes:

    ea is the eastl implementation: http://www.open-std.org/jtc1/sc22/wg...007/n2271.html

    [Array baseline is cost of reading/writing from a simple heap array. Hashes are generated using an Fnv1 hash; all maps use identical keys. Time is measured in cycles; lower is better. All optimizations are enabled]
    Code:
    [07:34:24]  --- Speed Test. ---
    [07:34:24]  --- Iteration Size = 256. ---
    [07:34:24]  --- HashTable Load Factor: 50 percent. ---
    [07:34:24]  
    [07:34:24] 
    [07:34:24] raw array baseline:   936
    [07:34:24] HashTable     insert: 11730
    [07:34:24] ea::hash_map  insert: 215982
    [07:34:24] std::hash_map insert: 240779
    [07:34:24] std::map      insert: 221015
    [07:34:24] std::map<str> insert: 648960
    [07:34:24] rde::hash_map insert: 24358
    [07:34:24]  
    [07:34:24] HashTable     find: 8054
    [07:34:24] ea::hash_map  find: 21791
    [07:34:24] std::hash_map find: 59153
    [07:34:24] std::map      find: 32327
    [07:34:24] std::map<str> find: 310925
    [07:34:24] rde::hash_map find: 25475
    [07:34:24]  
    [07:34:24] HashTable     remove: 25733
    [07:34:24] ea::hash_map  remove: 26042
    [07:34:24] std::hash_map remove: 46009
    [07:34:24] std::map      remove: 102566
    [07:34:24] std::map<str> remove: 174009
    [07:34:24] rde::hash_map remove: 9122
    [07:34:24]  
    [07:34:24] HashTable     find: 9262
    [07:34:24] ea::hash_map  find: 25003
    [07:34:24] std::hash_map find: 62802
    [07:34:24] std::map      find: 48260
    [07:34:24] std::map<str> find: 238944
    [07:34:24] rde::hash_map find: 22395
    [07:34:24]  
    [07:34:24]  --- Speed Test. ---
    [07:34:24]  --- Iteration Size = 384. ---
    [07:34:24]  --- HashTable Load Factor: 75 percent. ---
    [07:34:24]  
    [07:34:24] 
    [07:34:24] raw array baseline:   5460
    [07:34:24] HashTable     insert: 22976
    [07:34:24] ea::hash_map  insert: 149626
    [07:34:24] std::hash_map insert: 333290
    [07:34:24] std::map      insert: 373634
    [07:34:24] std::map<str> insert: 1070055
    [07:34:24] rde::hash_map insert: 69063
    [07:34:24]  
    [07:34:24] HashTable     find: 18781
    [07:34:24] ea::hash_map  find: 40914
    [07:34:24] std::hash_map find: 81796
    [07:34:24] std::map      find: 73832
    [07:34:24] std::map<str> find: 450250
    [07:34:24] rde::hash_map find: 38362
    [07:34:24]  
    [07:34:24] HashTable     remove: 17609
    [07:34:24] ea::hash_map  remove: 40812
    [07:34:24] std::hash_map remove: 64309
    [07:34:24] std::map      remove: 88554
    [07:34:24] std::map<str> remove: 288500
    [07:34:24] rde::hash_map remove: 17545
    [07:34:24]  
    [07:34:24] HashTable     find: 16240
    [07:34:24] ea::hash_map  find: 41548
    [07:34:24] std::hash_map find: 55731
    [07:34:24] std::map      find: 52404
    [07:34:24] std::map<str> find: 413939
    [07:34:24] rde::hash_map find: 28567
    [07:34:24]  
    [07:34:24]  --- Speed Test. ---
    [07:34:24]  --- Iteration Size = 512. ---
    [07:34:24]  --- HashTable Load Factor: 100 percent. ---
    [07:34:24]  
    [07:34:24] 
    [07:34:24] raw array baseline:   7902
    [07:34:24] HashTable     insert: 51780
    [07:34:24] ea::hash_map  insert: 214068
    [07:34:24] std::hash_map insert: 428346
    [07:34:24] std::map      insert: 389130
    [07:34:24] std::map<str> insert: 1315013
    [07:34:24] rde::hash_map insert: 70932
    [07:34:24]  
    [07:34:24] HashTable     find: 48481
    [07:34:24] ea::hash_map  find: 43351
    [07:34:24] std::hash_map find: 98816
    [07:34:24] std::map      find: 97720
    [07:34:24] std::map<str> find: 587472
    [07:34:24] rde::hash_map find: 54804
    [07:34:24]  
    [07:34:24] HashTable     remove: 108703
    [07:34:24] ea::hash_map  remove: 50633
    [07:34:24] std::hash_map remove: 104170
    [07:34:24] std::map      remove: 112113
    [07:34:24] std::map<str> remove: 273662
    [07:34:24] rde::hash_map remove: 7499
    [07:34:24]  
    [07:34:24] HashTable     find: 32895
    [07:34:24] ea::hash_map  find: 43203
    [07:34:24] std::hash_map find: 97939
    [07:34:24] std::map      find: 96576
    [07:34:24] std::map<str> find: 523633
    [07:34:24] rde::hash_map find: 362372
    First thing worth mentioning is that std::map<string> is just pure crap. If you don't actually need a self-balancing red-black tree that holds strings you should use something else in 100% of all cases. End of discussion. Also, std::*maps in general are just awful. eastl is simply better.

    At the end the numbers get a little squirrel-y. The order in which you insert keys also affects the clustering with open addressing. If I change the map sizes under 98-99% load, the results change for HashTable and rde::hash_map, though still stay roughly the same. The main point is that with any decent hash the backwards shifting does fix up the problem of the worst case under heavy load, and net you (generally) fast access times.

    So to summarize: I didn't actually accomplish anything useful today.


    [edit]
    source code: http://code.google.com/p/catastrophe...rs/HashTable.h
    Last edited by Gleeok; 07-17-2015 at 11:59 AM.
    This post contains the official Gleeok™ seal of approval. Look for these and other posts in an area near you.

  2. #2
    Now, count up your sins. mrz84's Avatar
    Join Date
    Jun 2001
    Location
    Randomness
    Age
    34
    Posts
    5,594
    Mentioned
    193 Post(s)
    Tagged
    8 Thread(s)
    vBActivity - Stats
    Points
    10,587
    Level
    30
    vBActivity - Bars
    Lv. Percent
    55%
    Daily Activity
    0%
    Weekly Activity
    25.93%
    Monthly Activity
    29.27%
    In other words, your day was like this: https://www.youtube.com/watch?v=0CB-MHu8zKI

    In other news, I have no idea what any of what that coding stuff is...despite taking 1 course during summer school in high school...about 10+years ago. Ya I got nothing.
    My Quotes and other siggy stuff.
    *Bar-Buddies updates whenever-also can email comics upon request*
    MP:89
    Playing: Too many to list now...
    Help this cat on his quest for World Domination!
    MydeviantART

  3. #3
    Quest Builder Anarchy_Balsac's Avatar
    Join Date
    Nov 2005
    Age
    34
    Posts
    655
    Mentioned
    7 Post(s)
    Tagged
    2 Thread(s)
    vBActivity - Stats
    Points
    2,060
    Level
    15
    vBActivity - Bars
    Lv. Percent
    5.37%
    Daily Activity
    0%
    Weekly Activity
    2.36%
    Monthly Activity
    8.65%
    Now Gleeok, you know as well as I do that using canned code does not mean using it as is. If it did, all users of XNA Game Studio's Platformer Starter Kit would be generic, non-scrolling platformers about Indian Jones ripoffs collecting yellow gems............

    Or to make a long story short, if there's pre-programmed hash maps, why not pick the one you like best, and mod it? Modifying it still makes it customized, but saves the headache of starting from scratch.

  4. #4
    Developer ZC Developer
    Gleeok's Avatar
    Join Date
    Apr 2007
    Posts
    4,623
    Mentioned
    211 Post(s)
    Tagged
    10 Thread(s)
    vBActivity - Stats
    Points
    12,171
    Level
    32
    vBActivity - Bars
    Lv. Percent
    39.83%
    Daily Activity
    0%
    Weekly Activity
    5.3%
    Monthly Activity
    38.59%
    Quote Originally Posted by mrz84 View Post
    In other words, your day was like this: https://www.youtube.com/watch?v=0CB-MHu8zKI
    Yep. Pretty much that minus that music and the swivel chair.

    Quote Originally Posted by Anarchy_Balsac View Post
    Now Gleeok, you know as well as I do that using canned code does not mean using it as is. If it did, all users of XNA Game Studio's Platformer Starter Kit would be generic, non-scrolling platformers about Indian Jones ripoffs collecting yellow gems............

    Or to make a long story short, if there's pre-programmed hash maps, why not pick the one you like best, and mod it? Modifying it still makes it customized, but saves the headache of starting from scratch.
    True. I usually wouldn't even bother modding it though. I have a bunch of different libraries installed so I'd just pick something from one of those normally. And I usually do. It's sort of I just had an idea and I usually just go for it. Plus, I already had a half-working HashMap anyway.

    This project has also sort of become a "from-scratch" project. Obviously I'm using libraries for sound and c# scripting, I'm not that crazy.
    This post contains the official Gleeok™ seal of approval. Look for these and other posts in an area near you.

  5. #5

    Armageddon Task Manager

    ctrl-alt-delete's Avatar
    Join Date
    Jul 2001
    Age
    30
    Posts
    3,302
    Mentioned
    52 Post(s)
    Tagged
    6 Thread(s)
    vBActivity - Stats
    Points
    9,936
    Level
    29
    vBActivity - Bars
    Lv. Percent
    74.17%
    Daily Activity
    0%
    Weekly Activity
    2.36%
    Monthly Activity
    3.33%
    Looking good. Now we just need you to make a website to host it. :-p


    <SUCCESSOR> Its Shadowblazer's dark essence invading the forums

  6. #6
    ZC Ambassador Tamamo's Avatar
    Join Date
    May 2011
    Location
    Kyoto
    Age
    28
    Posts
    759
    Mentioned
    82 Post(s)
    Tagged
    2 Thread(s)
    vBActivity - Stats
    Points
    4,854
    Level
    21
    vBActivity - Bars
    Lv. Percent
    87.56%
    Daily Activity
    0%
    Weekly Activity
    31.82%
    Monthly Activity
    47.24%
    @ctrl-alt-delete
    Oh come on Chief, surely you'll let him host it on AGN.
    @Gleeok
    Once the editor is ready for assets, do you think it'll be possible for me to help you with that?

  7. #7
    Developer ZC Developer
    Gleeok's Avatar
    Join Date
    Apr 2007
    Posts
    4,623
    Mentioned
    211 Post(s)
    Tagged
    10 Thread(s)
    vBActivity - Stats
    Points
    12,171
    Level
    32
    vBActivity - Bars
    Lv. Percent
    39.83%
    Daily Activity
    0%
    Weekly Activity
    5.3%
    Monthly Activity
    38.59%
    Quote Originally Posted by Tamamo View Post
    @Gleeok
    Once the editor is ready for assets, do you think it'll be possible for me to help you with that?
    The editor is already completed but it exists only in 4D space so I can't access it until I get a hold of an hyper-dimensional spaceship...


    Yeah... I could probably try and get the old editor to work with the new stuff. D: .. Won't be pretty but I don't really care.
    This post contains the official Gleeok™ seal of approval. Look for these and other posts in an area near you.

  8. #8
    ZC Ambassador Tamamo's Avatar
    Join Date
    May 2011
    Location
    Kyoto
    Age
    28
    Posts
    759
    Mentioned
    82 Post(s)
    Tagged
    2 Thread(s)
    vBActivity - Stats
    Points
    4,854
    Level
    21
    vBActivity - Bars
    Lv. Percent
    87.56%
    Daily Activity
    0%
    Weekly Activity
    31.82%
    Monthly Activity
    47.24%
    Me neither. As long as it works it works right... Right?

  9. #9
    Mad, Mad, Author ZoriaRPG's Avatar
    Join Date
    Oct 2006
    Location
    Prydon Academy
    Posts
    785
    Mentioned
    71 Post(s)
    Tagged
    1 Thread(s)
    vBActivity - Stats
    Points
    2,978
    Level
    17
    vBActivity - Bars
    Lv. Percent
    68.16%
    Daily Activity
    41.32%
    Weekly Activity
    61.28%
    Monthly Activity
    67.86%
    I sense a level of hyper-optimisation here.

    How refined is the cocaine that you use Gleeok, and where might I acquire some?


    Script Headers: RPG.zh ( v. a0.97.1 ) ( RPG.zh Thread ) | stdArguments.zh (v.6.9.9/1) | | Timers.zh (v.1.5)
    ZScript | ZC Dev | ZC 2.53 | Alucard's: stdCombos.zh (v1.1) | stdWeapons.zh | particles.z
    All of the code that I create and publish here is free for use, modification and distribution under the GPL v2.0.

  10. #10
    Gel
    Join Date
    Jul 2015
    Posts
    26
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    vBActivity - Stats
    Points
    187
    Level
    5
    vBActivity - Bars
    Lv. Percent
    7.44%
    Daily Activity
    0%
    Weekly Activity
    2.36%
    Monthly Activity
    3.33%
    I'm a bit late to the party.

    Hash tables are usually nothing fancy, but yours is pretty dang nice, I admit. I remember when I first heard of a hash table, I thought 'why didn't I think of that'- They're a pretty cool idea.
    I've seen some pretty impressive speed improvements by using a hash table. I admit, I also never liked STL, and often the word bloated to describe it; guess I'm part of the minority too!

    Although, I'm probably a little crazier, because I like writing everything from scratch (reinvent the wheel much).
    I'm going to try to make my own game console sometime in a few months, and I'll implement everything from it's blitting onto the screen, to controller input.
    There will definitely be no STL there! It's probably pretty redundant, but once it's done, cloning it would likely be easy. Maybe I'll give them as gifts.


    Obviously I'm using libraries for sound and c# scripting, I'm not that crazy
    I found this line particularly hurtful.

    I was never a fan of C# >.> So I'd probably create some sort of external C-like bytecode compiler, and bytecode interpreter.
    Again I reinvent the wheel so much I cry myself to sleep at night. I have a problem, and it affects my rate of completion. 0.o

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
About us
Armageddon Games is a game development group founded in 1997. We are extremely passionate about our work and our inspirations are mostly drawn from games of the 8-bit and 16-bit era.
Social