Interesting size reduction algorithm for HashTable

[Tommi Prami 130]

https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

[Stefan Glienke 2002]

Actually especially for a hashtable that algo is really terrible. It makes it super vulnerable against a non optimal hash function or heavy occurency of hash/bucket collisions.

 

Mod or anding with capacity-1 provides a better distribution.

[Tommi Prami 130]

If I understand that algorithm could be used for sizes that are prime also. Not sure would it matter tough. (Did not read it through, just browsed it, so I might not understand it too well)

Edited February 17, 2020 by Tommi Prami

[Arnaud Bouchez 407]

@Tommi Prami I guess you found out about Lemire in our latest commits - see e.g. https://github.com/synopse/mORMot/commit/a91dfbe2e63761d724adef0703140e717f5b2f00  🙂

 

@Stefan Glienke It is to be used with a prime size - as with our code - which also reduces memory consumption since power of 2 tables are far from optimal in this regard (doubling the slot numbers can become problematic).
With a prime, it actually enhances the distribution, even with a weak hash function, especially in respect to anding a power of 2.
Lemire reduction is as fast as anding a power of 2 since a multiplication is done in 1 cycle on modern CPUs.

 

Note that Delphi Win32 is not so good at compiling 64-bit multiplcation as involved with Lemire's, whereas FPC has no problem using the i386 mul opcode - which already gives 64-bit results.

Edited February 17, 2020 by Arnaud Bouchez

[Tommi Prami 130]

16 hours ago, Arnaud Bouchez said:

@Tommi Prami I guess you found out about Lemire in our latest commits - see e.g. https://github.com/synopse/mORMot/commit/a91dfbe2e63761d724adef0703140e717f5b2f00  🙂

 

Lucky guess 😄

 

 

16 hours ago, Arnaud Bouchez said:

 

@Stefan Glienke It is to be used with a prime size - as with our code - which also reduces memory consumption since power of 2 tables are far from optimal in this regard (doubling the slot numbers can become problematic).
With a prime, it actually enhances the distribution, even with a weak hash function, especially in respect to anding a power of 2.
Lemire reduction is as fast as anding a power of 2 since a multiplication is done in 1 cycle on modern CPUs.

Thanks for clarification

 

16 hours ago, Arnaud Bouchez said:

Note that Delphi Win32 is not so good at compiling 64-bit multiplcation as involved with Lemire's, whereas FPC has no problem using the i386 mul opcode - which already gives 64-bit results.

Could/Should you open ticket to the Embarcaredo bug tracker?

[Stefan Glienke 2002]

3 hours ago, Tommi Prami said:

Could/Should you open ticket to the Embarcaredo bug tracker?

Worthless, they give a crap about win32 codegen. There are way more severe issues open for ages...

[Guest]

3 hours ago, Tommi Prami said:

19 hours ago, Arnaud Bouchez said:

Note that Delphi Win32 is not so good at compiling 64-bit multiplcation as involved with Lemire's, whereas FPC has no problem using the i386 mul opcode - which already gives 64-bit results.

Could/Should you open ticket to the Embarcaredo bug tracker?

Just in case you decided to open a case ( Stefan was on point there ) : just suggest to adapt %10 of any other compiler out there do in according to arithmetical and mathematical optimized operation, looking at other compilers circa 2000 will do too, and will be huge progress.

[Tommi Prami 130]

On 2/18/2020 at 11:23 AM, Kas Ob. said:

Just in case you decided to open a case ( Stefan was on point there ) : just suggest to adapt %10 of any other compiler out there do in according to arithmetical and mathematical optimized operation, looking at other compilers circa 2000 will do too, and will be huge progress.

Don't quite understand what you are saying. Could you rephrase? 

[Tommi Prami 130]

On 2/18/2020 at 11:14 AM, Stefan Glienke said:

Worthless, they give a crap about win32 codegen. There are way more severe issues open for ages...

Most likely so, but on other hand without issue in bug tracker, chances it'll get fixed is even lower 😄  

[Guest]

2 hours ago, Tommi Prami said:

Don't quite understand what you are saying. Could you rephrase? 

I am trying to put this in useful sentence, but if they just looked at what any other compiler do and implement %10 of that, it will be great.

 

Please have a look at this small and short method:

 

type
  TEvent = procedure(Sender: TObject; Buffer: pointer; var Size: Integer) of object;

type
  TForm10 = class(TForm)
...
  private
    FEvent: TEvent;
    procedure DoEvent(Buffer: pointer; var Size: Integer);
..
  end;
..
procedure TForm10.FormCreate(Sender: TObject);
var
  Size: Integer;
begin
  DoEvent(nil, Size);
end;

procedure TForm10.DoEvent(Buffer: pointer; var Size: Integer);
begin
  if Assigned(FEvent) then
    FEvent(Self, Buffer, Size);
end;

I am after DoEvent, so lets see the assembly in 64bit:

 

 

Now, does that usage of CPU registers makes your stomach uncomfortable ? or not ? did the compiler miss using few more ? is the compiler behaving like a compiler in 2020 .

That code quality is almost every where, i honestly think a small tweaks in the compiler can decrease the size of the binary by %10.

That screenshot is from XE8 and Seattle have the same, a friend just confirmed it to me it is in Tokyo, so i think it is the same in every city.

That usage of register is so wrong, you know both parameters are in registers so all what do you need is to shift them according to the call convention, like rdx will be r8 and rcx will be rdx and self will be in rcx, so why the compiler spitting code like it diagnosed with Down Syndrome ? and which other compiler are so stupid to this.

 

 

In other word the ticket in case will be opened, it should be : reporting the wrong , essentially wrong in the compiler development itself, but not in single incident, because they are not single, like even from development, how such code is tested and measured, have they compared with other compilers?

 

Now honestly answer this, and i think it should be public vote, because i am interested what folks here think:

Which is worse ?

1) The people working on the compiler does know of this ? .... and they do nothing for any reason like (they don't give rat ass ) or (may be they are just busy with themes) ...etc, or they simply don't know how to make things better?

2) The people working on the compiler doesn't  know ?! like they really believe they are the fastest compiler out there and they should not change a thing, usually such code i call legacy no matter how perfect it is. 

 

Edited February 20, 2020 by Guest

[Anders Melander 1782]

1 hour ago, Kas Ob. said:

Which is worse ?

3) People assuming they know how and why Embarcadero prioritize as they do.

 

It's easy to sit here and bitch about this and that, when you're not the one responsible for these things. IMO it's just noise.

[Attila Kovacs 629]

8 minutes ago, Anders Melander said:

It's easy to sit here and bitch about this and that, when you're not the one responsible for these things

And meanwhile we are sitting here, money just falling out of our *nus, which we gladly forward to emba just for being collective responsible for whatever

[Anders Melander 1782]

10 minutes ago, Attila Kovacs said:

And meanwhile we are sitting here, money just falling out of our *nus

If you're losing money using Delphi then you should find another tool. I'm assuming that was what you meant, but I have a hard time parsing what you wrote.

[Attila Kovacs 629]

45 minutes ago, Anders Melander said:

If you're losing money using Delphi then you should find another tool.

Okay. This explains everything. This is the Message Of The Century.

[Vandrovnik 214]

3 hours ago, Anders Melander said:

3) People assuming they know how and why Embarcadero prioritize as they do.

 

It's easy to sit here and bitch about this and that, when you're not the one responsible for these things. IMO it's just noise.

May be Embarcadero could explain how they decide what to do and what to postpone... and postpone...? Because when I compare Embarcadero with TMS or Fastreport (or you), it is often reaction several years vs. several days, which I really do not like. Even https://quality.embarcadero.com/browse/RSP-24548, which should take +- 2 minutes to repair, will probably be there open for years. And please do not argument that it will take much more time because of testing, because the "testing" I can see each day in Object Inspector, which is not showing last letters in text (reported more than a year ago, but did they notice by themselves when testing?), and in Projects (which stops to show its content in 10.3.3 sometimes), and in Toolbars, which are moved randomly each day...

 

I would like to see a statistic, how reported and solved issues develop over years. May be it is somewhere on the web, I do not know.

[Anders Melander 1782]

11 minutes ago, Vandrovnik said:

May be Embarcadero could explain how they decide what to do and what to postpone... and postpone...? Because when I compare Embarcadero with TMS or Fastreport (or you), it is often reaction several years vs. several days, which I really do not like.

I don't like it either. Like everyone else I would love for every bug to be fixed yesterday, the compiler to produce better code, the VCL and RTL to support all the new shiny stuff and that my wife was 20 again. I'm assuming Embarcadero has the same wishes (Okay, maybe they don't care about my wife) but obviously their first priority is to make money. They're not in it for the Karma.

 

I myself used to be very vocal in the field test newsgroups in my critique of the decisions made by the various owners of Delphi during the years, to the point that I was asked not to participate in the field tests. So it's not like I don't understand the frustration or the need to vent it. However I also know that I don't know all about why they make the decisions they do. If I were in their shoes I might make the exact same decisions.

 

Of course they make mistakes. They make huge mistakes sometimes *cough* Delphi 8 *cough*. That is obvious to all. But it gets really tiresome to constantly read this whining about how bad Delphi is or how evil Embarcadero are. It's leading nowhere. Not a day goes by that I don't curse some part of Delphi to hell, but at the same time Delphi has payed for my house, my cars, my children's education and all my vacations.

 

Anyway, this has nothing to do with hash tables. Sorry for hijacking the thread.

[FredS 138]

37 minutes ago, Anders Melander said:

They're not in it for the Karma

 

OK but the 'don't complain' attitude is getting a little long in the tooth..

@Vandrovnik has a very valid argument, I've seen what he sees and there is NO VALID explanation for not updating things like the API for a decade or more..
 

Other than writing stuff about skins I guess 🙂

 

 

[Stefan Glienke 2002]

4 hours ago, Vandrovnik said:

I would like to see a statistic, how reported and solved issues develop over years. May be it is somewhere on the web, I do not know.

As for the publicly reported issues you can easily put that together yourself on the quality portal (JIRA) dashboard.

[Guest]

I enough time passed and you are cool down now, so let me put things one last time in place, and i am off to delete my account.

 

12 hours ago, Anders Melander said:

3) People assuming they know how and why Embarcadero prioritize as they do.

 

It's easy to sit here and bitch about this and that, when you're not the one responsible for these things. IMO it's just noise.

Andres, i respect every one, no matter how we think differently, i didn't attack single person, you went ahead and made personal attack, not cool man.

 

7 hours ago, Anders Melander said:

Of course they make mistakes. They make huge mistakes sometimes *cough* Delphi 8 *cough*. That is obvious to all. But it gets really tiresome to constantly read this whining about how bad Delphi is or how evil Embarcadero are. It's leading nowhere. Not a day goes by that I don't curse some part of Delphi to hell, but at the same time Delphi has payed for my house, my cars, my children's education and all my vacations.

See, i live mostly out of Delphi and i am addicted to it, yet i feel threaten in my livelihood, and all what left to me to do is exactly what i did, which is public shaming, just may be will help and give result, they have the resources and at least they should have the excuses and make them public. 

 

You see, when i asked in a question why on earth zero based strings are on by default on some platforms but not all, and the more important thing, why there is no magic compiler constant to reflect this, i can't remember the answer for the first, but the second i will not forget ever, it was because putting magic constant might break backward compatibility, how about that !.

 

Andres, almost all of my heroes and people i respect from years in programming are here and you are one of them !, i know just few people from Emarcadero and they are very nice and professional people, but not when it comes to such questions, they have nothing to answers, the other they decision makers don't freaking care, and you missed the point here, i am trying to do something about it, not by just ***, that shame on you to use such wording.

 

Again the only thing left is public shaming and may be they really don't know for god sake and all of the developer there and decisions makers are reading the tickets, because it is not one or two, it is the whole broken developing line, i was not expecting to be attacked in person, i was..., i don't have a plan and i didn't have plan or agenda, just releasing some steam and putting facts not many knows about, and there is till many many things to mention, but it seems i am offending people or making them angry, for that i am sorry.

 

 

Wish you all good luck and prosperity.

[Vandrovnik 214]

7 hours ago, Stefan Glienke said:

As for the publicly reported issues you can easily put that together yourself on the quality portal (JIRA) dashboard.

Well, I tried - but when I use (the top one) Export - Excel (all fields), it exports only 1000 issues of more then 16000... May be there is a better way and I just do not see it.

[Stefan Glienke 2002]

No need to export anything - JIRA has excellent charting - examples:

 

Edited February 21, 2020 by Stefan Glienke

[Sherlock 663]

4 hours ago, Kas Ob. said:

and i am off to delete my account.

Now please don't do that! I would say, that is a bit of an overreaction.

[Anders Melander 1782]

2 hours ago, Kas Ob. said:

Andres, i respect every one, no matter how we think differently, i didn't attack single person, you went ahead and made personal attack, not cool man.

There was nothing in what I wrote that was directed at you personally but if I have offended you I apologize for that.

 

I really do understand your POW and I agree with most of the problems you and others have, repeatedly, pointed to. What I object against is the one sided, two dimensional, demonization of Embarcadero.

 

I too have been down the road of a disgruntled customer. I experienced a great misalignment between the needs of me and my company as a customer and the direction Embarcadero took with Delphi. There was also the whole Resource Editor debacle, which I won't go into here. We knew from experience that complaining about things didn't make any difference, so we decided to vote with our money. After Delphi XE we cancelled all maintenance contracts and recommended to our clients that they do the same. Personally I stopped participating in the community and I no longer released any open source stuff. Basically I took my ball and went home. That was 10 years ago.

Around the time Delphi 10.2 was released I had finally cooled down. I had also come to the realization that the primary reason why I became a disgruntled customer in the first place was that my expectations were wrong. I had once seen Borland as "my friend" and I hadn't adjusted to the new reality of Delphi struggling to survive and stay relevant. I expected them to behave in a certain way and when they didn't I was disappointed. I not taking all the blame for that because they certainly tried to make us believe in the dream. I'm taking the blame for believing it.

[Vandrovnik 214]

5 hours ago, Stefan Glienke said:

No need to export anything - JIRA has excellent charting - examples:

 

Yeeees, that is exactly what I was searching for! Nice graphs (with sad data in it). Please can you tell me how to get these graphs from quality.embarcadero.com?

[Stefan Glienke 2002]

You will find information on google if you look for how to make queries and charts in jira.