PDA

View Full Version : This is how we roll



Gleeok
07-17-2015, 11:16 AM
(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. :P (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?! :weirdo:

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. :lmao: 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/wg21/docs/papers/2007/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]


[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. :nerd:


[edit]
source code: http://code.google.com/p/catastrophe/source/browse/trunk/Engine/include/Catastrophe/Core/Containers/HashTable.h

mrz84
07-17-2015, 09:47 PM
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. :shrug: Ya I got nothing.

Anarchy_Balsac
07-18-2015, 12:30 AM
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.

Gleeok
07-18-2015, 03:08 AM
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.


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. :P

ctrl-alt-delete
07-25-2015, 06:23 AM
Looking good. Now we just need you to make a website to host it. :-p

Tamamo
07-25-2015, 09:48 AM
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?

Gleeok
07-25-2015, 07:07 PM
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... :sonar:


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.

Tamamo
07-26-2015, 12:04 AM
Me neither. As long as it works it works right... Right?

ZoriaRPG
07-30-2015, 07:21 AM
I sense a level of hyper-optimisation here. :shocking:

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

_Mitch
07-31-2015, 12:12 AM
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

Anarchy_Balsac
07-31-2015, 12:26 AM
You know Gleeok, I think we have a member who can school us both on the coding front.

_Mitch
07-31-2015, 12:46 AM
Anarchy_Balsac I don't know about that. I'm pretty good, but I'm literally wasting my 20s on my computer. I'm only really knowledgeable in C and C++.
My notable skills are: networking, multiplayer, reverse engineering, and game design. I'm especially good at game design. I'm not really the best at coding in general.
I only know C, C++, Java, PHP, JS, HTML (which is a markup language), and x86 ASM. I'm much more of a low-level C guy though.
I'm not really that good at JS, I prefer to use emscripten (https://github.com/kripken/emscripten)to convert my C/C++ games to HTML5+JS.
I hate Java, and only learned it so I can write Android apps that use the API properly (the NDK still requires glue code).

I have to admit I also love x86 assembler. It's pretty beautiful once you get into it.
I think learning assembler was easier for me because of my EE background. Or it's just because I'm weird. 0.o

Learning x86 is the single most beneficial skill I think I have ever learned.
Once you understand get past the basics, you can pretty much reverse engineer anything.

Anarchy_Balsac
07-31-2015, 01:18 AM
_Mitch Wasting your life at your computer = being a programmer :D

Well, it can feel like that at times anyway. C and C++ are two of the most important programming languages. You can't count C# because it's just C++ with less overloading.

Gleeok
07-31-2015, 04:31 AM
I sense a level of hyper-optimisation here. :shocking:

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

It's not that it's supposed to be a drop-in replacement that's hyper optimized or anything, but more of just something that's lightweight and not stupid in general.


For you I will share the ultimate secret. You can get the good stuff at any quicky-mart: :D

3gkTbr2lrK4




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.


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

If you can turn a cheap last-gen smartphone into a full-blown OUYA-like console with a controller that outputs to a TV and will run emulators like SNES, PSX, etc you will be a god amongst nerds. :megaman:

I'm not really a fan of lua or dynamically-typed languages, and I wasn't really digging the angelscript for all the stuff I needed to do... so c# scripting at that point was a no brainer, really. The downside is that it is very time-consuming to bind everything properly--especially when you want quick proxy or place-holders for thing that aren't done yet.

_Mitch
07-31-2015, 03:41 PM
If you can turn a cheap last-gen smartphone into a full-blown OUYA-like console with a controller that outputs to a TV and will run emulators like SNES, PSX, etc you will be a god amongst nerds.

I'm not really a fan of lua or dynamically-typed languages, and I wasn't really digging the angelscript for all the stuff I needed to do... so c# scripting at that point was a no brainer, really. The downside is that it is very time-consuming to bind everything properly--especially when you want quick proxy or place-holders for thing that aren't done yet.

My console will not have Android OS though, that's for sure. I imagine it being OS-less, like the FAMICOM/NES! :]
I hear ya. I'm not a fan of lua or angelscript either (just because of the syntax alone)! :P
To be honest, I really hate dynamically typed languages! It just loses flexibility that way (and often performance).

C# isn't too bad, it's just I'm OCD about memory usage and stuff (probably because of my uC programming experience).
Complexity and flexibility usually come at the expense of speed (think c# scripting), unfortunately.
Sometimes you just have to juggle the value of a rolling it yourself and development time.

Also, the Ouya is a little disappointing, it's lower end than most phones, runs the same stuff, isn't portable.
At least Ouya gets a controller (even though most android apps are designed for touch screens).

ZoriaRPG
08-01-2015, 06:06 AM
My console will not have Android OS though, that's for sure. I imagine it being OS-less, like the FAMICOM/NES! :]
I hear ya. I'm not a fan of lua or angelscript either (just because of the syntax alone)! :P
To be honest, I really hate dynamically typed languages! It just loses flexibility that way (and often performance).

C# isn't too bad, it's just I'm OCD about memory usage and stuff (probably because of my uC programming experience).
Complexity and flexibility usually come at the expense of speed (think c# scripting), unfortunately.
Sometimes you just have to juggle the value of a rolling it yourself and development time.

Also, the Ouya is a little disappointing, it's lower end than most phones, runs the same stuff, isn't portable.
At least Ouya gets a controller (even though most android apps are designed for touch screens).

What implementation do you intend? Something that acts as a minimalistic HAL, with JIT cross-compiling? You'll need some kind of F/R OS though, for it to work. If you're going through all that effort, why not just do your own FPGA implementation, and aim for an ASIC? :cool:

I think you'll find that the sheer number of memory mappers for the NES/FC, and directly implementing them at an assembly level will be a gigantic stumbling block, particularly M90 mMC5, and VRC7.

I've liked what I've seen of AngelScript, primarily because it allows C, and C++ syntax, including a mixture of both; and it's a ZLIB license. It's still an interpreter though, and there is no real reason that you couldn't allow four different syntaxes to compile to the same engine... The main disadvantage of C# that it's designed for Windows, and I'm shaky on support for PSOX-based OSes, which is why I'd be wary of it, although admittedly, I haven;t enough experience to form an objective opinion...

Sorry Gleeok, but Posix OS compatibility is always high on my priority list. Besides, you'll never be happy until you write your own interpreter from scratch, and you know it.

Maybe I should make ZPASCAL or ZCOBOL90, to prove a point. Then I can take an extended leave to a padded resort!

_Mitch
08-01-2015, 10:42 PM
What implementation do you intend? Something that acts as a minimalistic HAL, with JIT cross-compiling? You'll need some kind of F/R OS though, for it to work. If you're going through all that effort, why not just do your own FPGA implementation, and aim for an ASIC?

I think you'll find that the sheer number of memory mappers for the NES/FC, and directly implementing them at an assembly level will be a gigantic stumbling block, particularly M90 mMC5, and VRC7.

I've liked what I've seen of AngelScript, primarily because it allows C, and C++ syntax, including a mixture of both; and it's a ZLIB license. It's still an interpreter though, and there is no real reason that you couldn't allow four different syntaxes to compile to the same engine... The main disadvantage of C# that it's designed for Windows, and I'm shaky on support for PSOX-based OSes, which is why I'd be wary of it, although admittedly, I haven;t enough experience to form an objective opinion...

Sorry Gleeok, but Posix OS compatibility is always high on my priority list. Besides, you'll never be happy until you write your own interpreter from scratch, and you know it.

Maybe I should make ZPASCAL or ZCOBOL90, to prove a point. Then I can take an extended leave to a padded resort!

I'm steering clear of FPGA for now. But I do intend on using it at some point; it's not a simple topic, and something I'd like a little practice with first (I have no real experience with hardware descriptive languages in the first place). My console won't be designed like the NES exactly, just similar in usage. I've never done anything with JIT compilation, have you (I'd like some tips)? JIT-compilation can be interesting but machine level compilers tend to be insanely complex, plus if I wrote my own I doubt I'd get decent performance out of it (except in a multiprocessor environment).

It'll be very simple in design, and use stuff I have in my junk drawer. I will be using an ATmega32 as a cheap video display controller (crazy, but it works), and a ARM cortex M3 (underpowered, but it's retro) for processing everything. I'm going to use NES controllers (just because I have a few). An SD card will store all the games in raw Intel HEX format, in individual directories (with graphics); on boot you choose one to play. Once a game is chosen, it'll re-program the micro with the game; It's basic, won't have a lot of memory, and no background processes running (just the game).

I admit I have been thinking about an FPGA like custom GPU- but I'll save that for another time; I'm sure it'll take a few months till I get anywhere. There won't be any removable cartridges, or (E)EPROM chips. I worked on an NES emulator once, pretty painful to be honest. I'm also hoping to make something easier to develop (6502 isn't my definition of easy, decimal support or not).

If I add any scripting to any game (on the console or not) I usually implement it with an external program that you write in, and compiles it into a bytecode. The interpreter is usually pretty basic; and (like the bytecode compiler) game/program specific. I prefer to use a switch statement, because of performance reasons (plus function pointers can be a pain to debug). But any scripting would be in a C-like syntax, of course. I would go into detail about past implementations, but that would just be a wall of text here. I've never combined both compiler and interpreter for a write and run environment before (never had to), but for complex stuff that would be helpful. I've never written GP scripting, only stuff embedded into a game (for map making).

If you design your own interpreter, it'll likely be faster (for the specific task / planned usage) and probably easier for you to write in (especially on memory constrained systems). Originally C# was designed for Windows, but it's just a language, and recently, I have seen Linux and Unix implementations. Similarly I have a thing against C# because of it's Microsoft orientation, and portability issues. I grudge against Microsoft for attempting to overthrow C++ with C#- but what I really hate is .NET and Microsoft's anti C agenda. The only real thing I have against angelscript is I didn't write it TBH :P.

BTW I didn't intend to hijack any threads, so I'll try to stop now (it's a bad habit I have). Also, sorry about the wall.

ZoriaRPG
08-02-2015, 09:44 AM
I'm steering clear of FPGA for now. But I do intend on using it at some point; it's not a simple topic, and something I'd like a little practice with first (I have no real experience with hardware descriptive languages in the first place). My console won't be designed like the NES exactly, just similar in usage. I've never done anything with JIT compilation, have you (I'd like some tips)? JIT-compilation can be interesting but machine level compilers tend to be insanely complex, plus if I wrote my own I doubt I'd get decent performance out of it (except in a multiprocessor environment).

It'll be very simple in design, and use stuff I have in my junk drawer. I will be using an ATmega32 as a cheap video display controller (crazy, but it works), and a ARM cortex M3 (underpowered, but it's retro) for processing everything. I'm going to use NES controllers (just because I have a few). An SD card will store all the games in raw Intel HEX format, in individual directories (with graphics); on boot you choose one to play. Once a game is chosen, it'll re-program the micro with the game; It's basic, won't have a lot of memory, and no background processes running (just the game).

I admit I have been thinking about an FPGA like custom GPU- but I'll save that for another time; I'm sure it'll take a few months till I get anywhere. There won't be any removable cartridges, or (E)EPROM chips. I worked on an NES emulator once, pretty painful to be honest. I'm also hoping to make something easier to develop (6502 isn't my definition of easy, decimal support or not).

If I add any scripting to any game (on the console or not) I usually implement it with an external program that you write in, and compiles it into a bytecode. The interpreter is usually pretty basic; and (like the bytecode compiler) game/program specific. I prefer to use a switch statement, because of performance reasons (plus function pointers can be a pain to debug). But any scripting would be in a C-like syntax, of course. I would go into detail about past implementations, but that would just be a wall of text here. I've never combined both compiler and interpreter for a write and run environment before (never had to), but for complex stuff that would be helpful. I've never written GP scripting, only stuff embedded into a game (for map making).

If you design your own interpreter, it'll likely be faster (for the specific task / planned usage) and probably easier for you to write in (especially on memory constrained systems). Originally C# was designed for Windows, but it's just a language, and recently, I have seen Linux and Unix implementations. Similarly I have a thing against C# because of it's Microsoft orientation, and portability issues. I grudge against Microsoft for attempting to overthrow C++ with C#- but what I really hate is .NET and Microsoft's anti C agenda. The only real thing I have against angelscript is I didn't write it TBH :P.

BTW I didn't intend to hijack any threads, so I'll try to stop now (it's a bad habit I have). Also, sorry about the wall.


My only tip for the present: Design your USB to SSR bridge PIC to use dual 4021 SSRs as inputs. That will give you SNES/SuFami, and NES/FC controller support, with no sacrifices. I did some basic JIT stuff in the past, but applicability to this project, is rather thin. As to FPGA design, the best thing, is to jump into it head first, and play with it, so that you can acclimate. It's the ultimate fusion of SE and EE, and depends on knowing the logic of both. There are tools to convert schem designs into FPGA instructions, but I can't attest to the best of those, at present.

If you want to discuss it further, a new topic would probably be best.

Regarding C#: Taking something that works, that everyone understands, and hijacking it, to make something proprietary, is exactly what Microsoft do as daily business. I'm more shocked that it can be used withotut .NET on Posix OSes. (I never expected that, and anticipated more of a boycott from the OSS community, regarding .NET reliance.)

Gleeok
08-03-2015, 02:47 AM
Microsoft .NET and Java mentality are the reasons it takes newer versions of stuff to take 1000 times longer to open. Considering that computers are like magnitudes faster now than they used to be I have pretty much just given up on the entire human race as a species to actually care about things...

But! On the flip side: I'm using mono, which is cross-platform. Plus, I have to say that c# is a great high-level language; I can't wait until all this other stuff is out of the way and I can just work mostly on scripts for a change. :)


Also, as a side note: That;s entirely way too many computer-techy acronyms too handle. :P

Gleeok
02-19-2017, 08:37 AM
Just a little follow up here. I've been cleaning up a lot of unused code (by that I mean ripping out things only used from older projects into a separate library) and sanitizing some things in the process, and this hashtable happened to get caught up in it, so I went ahead and optimized it and ran the benchmark again for fun. :)

I also removed most of the template code for the new version, to optimize for compile times and code bloat as well. I have a template bloat test that I run (it's basically a code generator from macros) which creates a bunch of instantiations of templates; this beats any std::anything compile times by a ridiculous margin, and only generates <1% code bloat by comparison, apparently, so I'm satisfied enough.

This time I upped the value size to at least try and give chained-hashing a good run, but it's even worse than before...

*Note*
HashTable = original version.
HashTable2 = new version.


[03:33:46] --- Speed Test. ---
[03:33:46] --- Iteration Size = 512. ---
[03:33:46] --- HashTable Load Factor: 50 percent. ---
[03:33:46]
[03:33:46] sizes 0, 0, 0, 0
[03:33:46] raw array baseline: 3207
[03:33:46] HashTable insert: 134018
[03:33:46] HashTable2 insert: 103645
[03:33:46] ea::hash_map insert: 585884
[03:33:46] std::hash_map insert: 640239
[03:33:46] std::map insert: 529085
[03:33:46] std::map<str> insert: 967153
[03:33:46] rde::hash_map insert: 185046
[03:33:46]
[03:33:46] sizes 511, 511, 511, 511
[03:33:46] HashTable clear: 43197
[03:33:46] HashTable2 clear: 6711
[03:33:46] ea::hash_map clear: 230845
[03:33:46] std::hash_map clear: 275579
[03:33:46] std::map clear: 480117
[03:33:46] std::map<str> clear: 19228
[03:33:46] rde::hash_map clear: 84533
[03:33:46]
[03:33:46] sizes 0, 0, 0, 0
[03:33:46] HashTable insert: 268658
[03:33:46] HashTable2 insert: 278309
[03:33:46] ea::hash_map insert: 487562
[03:33:46] std::hash_map insert: 795025
[03:33:46] std::map insert: 938527
[03:33:46] std::map<str> insert: 1060380
[03:33:46] rde::hash_map insert: 241995
[03:33:46]
[03:33:46]
[03:33:46] sizes 511, 511, 511, 511
[03:33:46] HashTable find: 62056
[03:33:46] HashTable2 find: 13803
[03:33:46] ea::hash_map find: 87671
[03:33:46] std::hash_map find: 75523
[03:33:46] std::map find: 147322
[03:33:46] std::map<str> find: 189381
[03:33:46] rde::hash_map find: 18451
[03:33:46]
[03:33:46]
[03:33:46] sizes 511, 511, 511, 511
[03:33:46] HashTable remove: 53568
[03:33:46] HashTable2 remove: 53844
[03:33:46] ea::hash_map remove: 60767
[03:33:46] std::hash_map remove: 146094
[03:33:46] std::map remove: 121547
[03:33:46] std::map<str> remove: 87439
[03:33:46] rde::hash_map remove: 35045
[03:33:46]
[03:33:46]
[03:33:46] sizes 383, 383, 383, 383
[03:33:46] HashTable find: 28340
[03:33:46] HashTable2 find: 5939
[03:33:46] ea::hash_map find: 36020
[03:33:46] std::hash_map find: 64632
[03:33:46] std::map find: 128579
[03:33:46] std::map<str> find: 144129
[03:33:46] rde::hash_map find: 104023
[03:33:46]
[03:33:46] --- Speed Test. ---
[03:33:46] --- Iteration Size = 768. ---
[03:33:46] --- HashTable Load Factor: 75 percent. ---
[03:33:46]
[03:33:46] sizes 0, 0, 0, 0
[03:33:46] raw array baseline: 4816
[03:33:46] HashTable insert: 260679
[03:33:46] HashTable2 insert: 254548
[03:33:46] ea::hash_map insert: 376892
[03:33:46] std::hash_map insert: 1259679
[03:33:46] std::map insert: 892279
[03:33:46] std::map<str> insert: 1188773
[03:33:46] rde::hash_map insert: 301241
[03:33:46]
[03:33:46] sizes 767, 767, 767, 767
[03:33:46] HashTable clear: 100992
[03:33:46] HashTable2 clear: 10515
[03:33:46] ea::hash_map clear: 441884
[03:33:46] std::hash_map clear: 349907
[03:33:46] std::map clear: 565421
[03:33:46] std::map<str> clear: 37769
[03:33:46] rde::hash_map clear: 66423
[03:33:46]
[03:33:46] sizes 0, 0, 0, 0
[03:33:46] HashTable insert: 336994
[03:33:46] HashTable2 insert: 260514
[03:33:46] ea::hash_map insert: 552926
[03:33:46] std::hash_map insert: 952609
[03:33:46] std::map insert: 1278542
[03:33:46] std::map<str> insert: 1504508
[03:33:46] rde::hash_map insert: 286960
[03:33:46]
[03:33:46]
[03:33:46] sizes 767, 767, 767, 767
[03:33:46] HashTable find: 103123
[03:33:46] HashTable2 find: 19976
[03:33:46] ea::hash_map find: 279149
[03:33:46] std::hash_map find: 356751
[03:33:46] std::map find: 123995
[03:33:46] std::map<str> find: 432412
[03:33:46] rde::hash_map find: 132491
[03:33:46]
[03:33:46]
[03:33:46] sizes 767, 767, 767, 767
[03:33:46] HashTable remove: 53389
[03:33:46] HashTable2 remove: 30244
[03:33:46] ea::hash_map remove: 162388
[03:33:46] std::hash_map remove: 184580
[03:33:46] std::map remove: 175415
[03:33:46] std::map<str> remove: 168393
[03:33:46] rde::hash_map remove: 17975
[03:33:46]
[03:33:46]
[03:33:46] sizes 575, 575, 575, 575
[03:33:46] HashTable find: 26669
[03:33:46] HashTable2 find: 14989
[03:33:46] ea::hash_map find: 55588
[03:33:46] std::hash_map find: 280343
[03:33:46] std::map find: 112630
[03:33:46] std::map<str> find: 304988
[03:33:46] rde::hash_map find: 129425
[03:33:46]
[03:33:46] --- Speed Test. ---
[03:33:46] --- Iteration Size = 1024. ---
[03:33:46] --- HashTable Load Factor: 100 percent. ---
[03:33:46]
[03:33:46] sizes 0, 0, 0, 0
[03:33:46] HashTable insert: 358430
[03:33:46] HashTable2 insert: 343127
[03:33:46] ea::hash_map insert: 951636
[03:33:46] std::hash_map insert: 1230571
[03:33:46] std::map insert: 1690042
[03:33:46] std::map<str> insert: 2068730
[03:33:46] rde::hash_map insert: 456155
[03:33:46]
[03:33:46]
[03:33:46] sizes 1023, 1023, 1023, 1023
[03:33:46] HashTable find: 156528
[03:33:46] HashTable2 find: 23810
[03:33:46] ea::hash_map find: 174245
[03:33:46] std::hash_map find: 227375
[03:33:46] std::map find: 353819
[03:33:46] std::map<str> find: 665612
[03:33:46] rde::hash_map find: 85126
[03:33:46]
[03:33:46]
[03:33:46] sizes 1023, 1023, 1023, 1023
[03:33:46] HashTable remove: 114643
[03:33:46] HashTable2 remove: 84462
[03:33:46] ea::hash_map remove: 205326
[03:33:46] std::hash_map remove: 309403
[03:33:46] std::map remove: 248285
[03:33:46] std::map<str> remove: 430286
[03:33:46] rde::hash_map remove: 64323
[03:33:46]
[03:33:46]
[03:33:46] sizes 767, 767, 767, 767
[03:33:46] HashTable find: 149344
[03:33:46] HashTable2 find: 18428
[03:33:46] ea::hash_map find: 193752
[03:33:46] std::hash_map find: 295686
[03:33:46] std::map find: 143338
[03:33:46] std::map<str> find: 171214
[03:33:46] rde::hash_map find: 1065822
[03:33:46]
[03:33:46] --- Worst case test ---
[03:33:46]
[03:33:46] sizes 0, 0, 0, 0
[03:33:46] HashTable insert: 242623
[03:33:46] HashTable2 insert: 266851
[03:33:46] std::hash_map insert: 651776
[03:33:46] std::map insert: 521774
[03:33:46] rde::hash_map insert: 284348
[03:33:46]
[03:33:46] --- HashTable Load Factor: 50 percent. ---
[03:33:46]
[03:33:46] sizes 512, 512, 512, 512
[03:33:46] HashTable find: 44821
[03:33:46] HashTable2 find: 8608
[03:33:46] std::hash_map find: 268987
[03:33:46] std::map find: 134476
[03:33:46] rde::hash_map find: 21596
[03:33:46] HashTable remove: 47197
[03:33:46] HashTable2 remove: 8031
[03:33:46] std::hash_map remove: 234941
[03:33:46] std::map remove: 257659
[03:33:46] rde::hash_map remove: 14391
[03:33:46]
[03:33:46] --- HashTable Load Factor: 25 percent. ---
[03:33:46]
[03:33:46] sizes 256, 256, 256, 256
[03:33:46] HashTable find: 41936
[03:33:46] HashTable2 find: 3722
[03:33:46] std::hash_map find: 55741
[03:33:46] std::map find: 53282
[03:33:46] rde::hash_map find: 38327
[03:33:46] HashTable insert: 175521
[03:33:46] HashTable2 insert: 176591
[03:33:46] std::hash_map insert: 509196
[03:33:46] std::map insert: 435533
[03:33:46] rde::hash_map insert: 256612
[03:33:46]
[03:33:46] --- HashTable Load Factor: 67 percent. ---
[03:33:46]
[03:33:46] sizes 683, 683, 683, 683
[03:33:46] HashTable find: 125480
[03:33:46] HashTable2 find: 20572
[03:33:46] std::hash_map find: 357002
[03:33:46] std::map find: 286201
[03:33:46] rde::hash_map find: 135255
[03:33:46] HashTable insert: 4739951
[03:33:46] HashTable2 insert: 176813
[03:33:46] std::hash_map insert: 888408
[03:33:46] std::map insert: 372748
[03:33:46] rde::hash_map insert: 204137
[03:33:46]
[03:33:46] --- HashTable Load Factor: 83 percent. ---
[03:33:46]
[03:33:46] sizes 848, 848, 848, 848
[03:33:46] HashTable find: 408489
[03:33:46] HashTable2 find: 285519
[03:33:46] std::hash_map find: 248305
[03:33:46] std::map find: 168740
[03:33:46] rde::hash_map find: 131819
[03:33:46] HashTable remove: 2152647
[03:33:46] HashTable2 remove: 701855
[03:33:46] std::hash_map remove: 194693
[03:33:46] std::map remove: 214543
[03:33:46] rde::hash_map remove: 49955
[03:33:46]
[03:33:46] --- HashTable Load Factor: 63 percent. ---
[03:33:46]
[03:33:46] sizes 647, 647, 647, 647
[03:33:46] HashTable find: 144374
[03:33:46] HashTable2 find: 91816
[03:33:46] std::hash_map find: 175481
[03:33:46] std::map find: 142534
[03:33:46] rde::hash_map find: 112440


2nd moral of the story?

Don't use std:: for anything. It's all shit crap fucking stupid. Just including the single hashmapTest.h file increased my compile time by over 400% making me very sad, so this is definitely the last time I ever randomly benchmark c++ things.

It sounds like I'm ranting now so I'll call it a day. :P
One of these days in the near future I plan to put up a bunch of single file libs on github. Not like anybody will ever use them, but hey, why not.