flat assembler
Message board for the users of flat assembler.

Index > Heap > hashing function

Author
Thread Post new topic Reply to topic
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Since my mathematical abilities are exceptionaly bad I need help for optimize this code:
Code:
function hash(dni: longint; buckets: longint): longint;
begin
  dni := dni mod buckets;

  if dni mod INTERVAL = (INTERVAL-1) then dec(dni);

  hash:= dni;
end;    


Is there a way to avoid the use of "if"? buckets is multiple of INTERVAL and at every INTERVAL buckets one is reserved for overflows.

Thanks!

PS: Note that if the solution adds another DIV/MOD then I prefer the "if" because the misprediction possibly take less time than the DIV instruction.
Post 24 Aug 2006, 20:52
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
just a note: if chance for "if" condition being true is very small, then prediction hint may work.
Post 24 Aug 2006, 22:10
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
So it can't be done in a better way than this?
Code:
hash:; EAX=dni; ECX=buckets
     push    ebx

     xor     edx, edx
     div     ecx
     mov     eax, edx

     mov     ecx, edx
     mov     ebx, INTERVAL
     xor     edx, edx
     div     ebx
     mov     eax, ecx
     cmp     edx, INTERVAL-1
     jne     .ok

     dec     eax
.ok:
     pop     ebx
     ret
    


PS: BTW, I used longint because Turbo Pascal does not support cardinal (unsigned long).
Post 24 Aug 2006, 23:39
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7740
Location: Kraków, Poland
Tomasz Grysztar
Quote:
Code:
     cmp     edx, INTERVAL-1
     jne     .ok
     dec     eax
.ok:    

EDX cannot be larger than INTERVAL-1 here, thus if you substract the INTERVAL-1 from EDX, the carry will not occur only when EDX is exactly INTERVAL-1. So the above can be rewritten without a jump:
Code:
     cmp     edx,INTERVAL-1
     adc     eax,-1    
Post 25 Aug 2006, 09:17
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
NICE!!! Very Happy

Thanks!!
Post 25 Aug 2006, 13:05
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
Cute Smile
Post 25 Aug 2006, 15:21
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
This is what most programmers simply beware of, because they are either lazy or stupid Wink

I mean that's why I like asm -- it makes you think low-level, taking a more intellectual approach. Of course, that code could have been written in HLLs as well (or well at least "eliminating the if"), but HLL guys will never do that because of their restrictive thinking.

I always love these kind of "tricks" since it exploits our intellectual and thinking capabilities rather than selecting brute-force solutions, like most people do. And in all of this, asm and math help a lot. If you like asm, you also like "tricks" like this, even if it isn't obvious. Wink

_________________
Previously known as The_Grey_Beast
Post 28 Aug 2006, 13:02
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Quote:

Of course, that code could have been written in HLLs as well (or well at least "eliminating the if"),


How?

I wrote it in Pascal because it's for an exercise of Introduction to Databases course of my faculty and well, they ask us for doing it in Pascal... It doesn't matter for them if the code isn't optimal, for them is enough that the code doesn't make too much disk accesses when it can be done in fewer accesses but I can't tolerate write simple functions not optimal Razz

Regards
Post 28 Aug 2006, 13:58
View user's profile Send private message Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
locodelassembly wrote:
How?
I have no experience with Pascal, so I can't really start to tell. I didn't say it can be done. I said it "could" (like in perhaps, you know Wink). Also, I think it can be done in C, which is a HLL too, but I can't figure out right now.

locodelassembly wrote:
I can't tolerate write simple functions not optimal
I agree here. I usually try to use my intellectic (Smile) approach to optimize functions on the basic level, like this one, even if it isn't actually "worth" the speed for some people (I think you know who I'm referring to... Smile). It just makes me feel better than knowing I could have optimized it, but instead chose the damn brute-force solution.
Post 28 Aug 2006, 14:10
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Code:
program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  INTERVAL = 5;


function hash(dni: longint; buckets: longint): longint;
begin
  dni := dni mod buckets;

  if dni mod INTERVAL = (INTERVAL-1) then dec(dni);

  hash:= dni;
end;

function hash2(dni: longint; buckets: longint): longint;
begin
  dni := dni mod buckets;

  dni := dni - ((INTERVAL-2 - (dni mod INTERVAL)) shr 31);

  hash2:= dni;
end;

function hashASM(dni: longint; buckets: longint): longint; assembler;
asm
     push    ebx 

     mov     ecx, edx
     xor     edx, edx
     div     ecx
     mov     eax, edx

     mov     ecx, edx
     mov     ebx, INTERVAL
     xor     edx, edx
     div     ebx
     mov     eax, ecx

     cmp     edx,INTERVAL-1
     adc     eax,-1

     pop     ebx
     ret
end;


var
  i: integer;

begin
  for i := 0 to 23 do
    WriteLn(Hash(i, 50000), ';', HashASM(i, 50000), ';', hash2(i, 50000), ';', i);
  ReadLn;
end.    


I found how Very Happy
Post 28 Aug 2006, 16:20
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Code:
function hash2(dni: longint; buckets: longint): longint; 
begin 
  dni := dni mod buckets; 

  hash2:= dni - ((INTERVAL-2 - (dni mod INTERVAL)) shr 31); 
end;    


I forgot to warn that if you translate it to C "shr 31" is interpreted as "sar 31" so in C you must use "dni + ..." instead of "dni - ..." or change the type to unsigned long Razz

Regards
Post 28 Aug 2006, 20:23
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
I still haven't found a quick-and-easy way to make VC++ generate something as elegant as the CMP/ADC solution Smile
Post 28 Aug 2006, 23:08
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Like http://board.flatassembler.net/topic.php?p=40239#40239 there are some things that you can't convert to HLL Wink
Post 29 Aug 2006, 14:24
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
locodelassembly wrote:
Like http://board.flatassembler.net/topic.php?p=40239#40239 there are some things that you can't convert to HLL Wink


Even that kind of code can be written in C... but it won't be pretty, and most likely won't generate as pretty machine code either Smile

_________________
Image - carpe noctem
Post 29 Aug 2006, 14:40
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
I think you should see "Generalized shift" in http://www.azillionmonkeys.com/qed/asmexample.html that the VC++ is able to produce sbb() instruction. This means that is is aware of this instruction which gives hope Smile
Post 29 Aug 2006, 15:04
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
There is always hope... use "__asm" Wink
Post 29 Aug 2006, 19:08
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
Madis731 wrote:
I think you should see "Generalized shift" in http://www.azillionmonkeys.com/qed/asmexample.html that the VC++ is able to produce sbb() instruction. This means that is is aware of this instruction which gives hope Smile


But, if I understand that page correctly, this is by (ab)using an implementation-specific detail... I'd rather write in assembly, then (and/or use a less pretty but portable construct).

I pretty much avoid __asm... it's somewhat unportable between C++ compilers, and if a piece of code is worth writing in assembly, it's usually worth writing in a decent external assembler (fasm comes to mind Wink).

_________________
Image - carpe noctem
Post 29 Aug 2006, 23:03
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
also i heard "__asm" is no longer supported on 64bit MSVC
Post 30 Aug 2006, 05:24
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.