Fast search using hashing.

Greetings, All! Initially, this article was intended for the ZX-Pilot newspaper, but, because... about fate I haven’t heard anything from this newspaper for six months, so I decided to throw it here. I think It will be useful for you to read too. So, we will talk about such a useful thing as quickly searching for information on example of searching for assembler tags in the table. This example was not selected by chance - at the moment your humble servant is studying (don’t think something bad) by writing your own assembler. Let's skip the reasons why I decided to make my own assembler, but immediately let's get down to business. So, each mark has its own name and meaning, for the sake of which it is necessary search for a label throughout the table. Objective: to ensure that the label is entered into the table as quickly as possible the first pass and find it as quickly as possible on the second pass. Solution 1. Dumb and the first one that came to mind. Sequential method search. The memory for the tag is distributed as follows: +0 byte - length of the label name (1-15) and all sorts of flag bits. +1..+[+0] - symbols of the label name +[+0]+1..+[+0]+2 - label value. The search algorithm is simple: 1. Compare the length of the desired label and the current one, if they are not equal, then repeat step 1 for the next mark. 2. We compare the symbols of the labels in approximately the same way: ;sp - address in the label table ;cf=0pop hl; popped 2 characters of the current label from the stack ld de,nn;nn - symbols of the searched label sbc hl,de;16-bit cp jr nz, point 1; if not equal then point 1 3. If found, then take the value of the label, otherwise - bummer. It is not difficult to calculate that even with such a fast method of comparing characters marks (42 measures per word) with the number of marks of length equal to the length of the searched one marks equal to 100, the search time will be about 6300 cycles only on comparison of symbols. I did not take into account the time of screening by length and all sorts of recalculations. That's why I decided to use a much faster method. Solution 2. Hashing method with linear collision avoidance probe method. I’ll say right away that I didn’t come up with this myself, but heard it at lectures on structures and algorithms for data processing. So, what is the hashing method based on? Hashing is the calculation of the address of an element in a table using its key. So, for us, the role of an element is played by the assembler label. In your In this case, this could be either a phone number, or a word in the dictionary, or maybe one of the fields in the database. We will consider the key to be a number that is calculated based on one or more element fields. In our case, the key value calculated from the label name. It remains to decide on the function by which the calculation will take placekey (it is usually called a HASH FUNCTION). There's a lot of room for your imagination. Requirements that a hash function must satisfy: 1. It must be calculated simply and elegantly. You can even use table. 2. It should show an approximately even distribution of numbers keys regardless of the field name. In our case, no matter what labels are used (name length and characters). probability of receiving keys should be approximately the same. A good hash function is the algebraic sum of the character codes of the label name. The resulting key is calculated using the formula: k=H mod N, where H is a hash function, N is a natural number. As N It is convenient to use the number 2^n, where n is also a natural number. In this In this case, everything is much simpler: k=H and (2^n-1). Now let's move directly to the algorithm for creating and searching for tags. Labels are stored in memory as follows: In one memory area, the actual marks themselves are stored, stored as in sequential search method The addresses of these same tags are stored in another area. This table is preceded by a small table n bytes long, which stores the number tags with the same key. Unlike the previous table, the address table (when creating a label table) is not filled in sequentially, but according to the following algorithm: 1. Based on the label name, its key is calculated. 2. In the table preceding the table of addresses, we look at how many labels with a given key. Next, you need to check whether a label with the same name exists in table to avoid duplicate labels: ;SP- ADDRESS IN ADDRESS TABLE ;B-LENGTH OF THE CREATED MARK ;C=15 POP HL; TAKE THE ADDRESS OF THE MARK LD A,(HL); CONTAINS LABEL LENGTH AND FLAGS (USED, DEFINED, ETC) AND C CP B; COMPARE THE LENGTH JR Z,CHECK_SYMBOLS;IF THE LENGTHS OF THE FOUND AND CREATED MARKS COINCIDE, THEN ;COMPARING THEIR SYMBOLS ... TOTAL - 35 BARKS PER MARK. If a label already exists in the table, then generate an error of type label exists. Otherwise, we create a new label and add its address to the address table. Searching for a label (especially the inner loop search) is basically the same as creation, with the only difference that you don’t need to create anything. Memory consumption: Each label descriptor consumes 2 bytes, but not one should naively believe that the total amount spent will be (2*number labels + total length of label names) bytes. It will actually be spent somewhat more, since some keys will appear more often than others, so the memory costs will be like this: (2*N*M+total length of tag names), where M is the number of tags with the most frequently occurring key.However, despite this, the game is worth the candle. Here is a specific example: when number of labels with a length from 2 to 11 characters equal to 522, the following were obtained results: N Len C 4 1104 138 8 1184 74 16 1280 40 32 1536 24 64 1920 15 128 2816 11 256 4096 8 For those who do not quite understand: N is a parameter from the hash function, Len is the length tag address tables, C - maximum number of tag search cycles. Number effective search cycles (i.e. those in which it is necessary to compare tag symbols) is several times less than the average number of search cycles, because First, the lengths of the marks are compared, and then, if the lengths match, the symbols are compared. In addition, according to probability theory, the average number of search cycles will be somewhere 2 times less than indicated in the table. In total, you will have to compare symbols for about 20% of the labels located in the table. The results are really impressive: with N equal to 256, the Average number of labels, which must be checked to find (or not find) a mark, about 256 times less than the number of labels in the table. Cool, right? I will most likely make it possible to manually select the parameter N, so that owners of cars with large memory sizes can be sure that that the benefit from their memory will be not only in its quantity, but also in speedsearch for marks, because they will be able to afford to set the N parameter to 256. Perhaps, if I can quickly perform calculations, it will be introduced hashing search method based on name collision resolution method Quadratic Trial, which reduces the number of attempts to find a mark in C^(1/2) times compared to the Linear Sample method, where C is the number from the table. If anyone has suggestions for improving the algorithm, do not hesitate to write. P.S. Theoretically, the speed of assembly of commands like ldi, neg, cpl, nop will be no more than: on the first pass - 80 cycles/command. on the second pass - 160 cycles/command. I wish you health, happiness and creative Uzbeks. Aleksey Malov aka VIVID/Brainwave.

Greetings, Dmitry! Thu 30 Mar 2000 at 22:33:04 Dmitry Lomov and Aleksey Malov were talking on the topic Quick search using hashing.. DL> in vain. DL> what are the main ideological points of the intended assembler? Convenience in terms of interface (I don’t like Alasm because of this), availability local tags (useful thing), high speed (Zasm infuriates), and support my 1Mb Simm (No one except Alasm understands above 128k, but Alasm not convenient). Well, the only thing Storm lacks is a multicolor screensaver ;). AM>> A good hash function is the algebraic sum of character codes AM>> label name. DL> bad, bad, you can trust me. I won’t justify it theoretically (yes DL> and it won’t work ;) , I’ll just say that if I use only in labels DL> large Latin letters and numbers, the effectiveness of the method will drop by half DL> seven. It's better to use XOR with cyclic shifts. when I do this DL> I was studying, I went through many options... I settled on this one. It is planned to store tags in tokenized form, because the following character sequences: loop, LOOP, ER,er, bank,BANK, ETC.occur quite often and will save on memory and search speed somewhat will increase, and this will result in a more or less decent spread of keys. DL> XOR first DL> RRCA DL> XOR second DL> RRCA DL> ... We must try... DL> the best option is to calculate the CRC of all letters of the label, possibly including DL> there is also a length byte. option - CRC8, the optimal polynomial is calculated Could you tell us more about the CRC calculation algorithm? DL> provide a detailed description of your method, and in return you will receive mine ;) Memory for tags is planned to be allocated as follows: the labels, along with their values, grow sequentially from top to bottom. pointers to the labels are located below: [memory for m pointers to labels with key 0] [memory for m pointers to labels with key N-1] m is a power of two. The search is like this: 1. Calculate the key for the desired tag using some algorithm. 2. Next, look in a separate table to see how many pointers to labels there are with with this key. 3. set sp to the beginning of the table of pointers to labels with this key. 4. B is the length of the desired mark. 5. in C-#0f, because ml. The 4 bits of the label flag store its length. 6. and let's go compare the lengths of the markspop hl ;take the address of the label, it contains the length of the label, and immediately after it - ;symbols and meaning. ld a,(hl) ;take the length and c ;discard unnecessary bits cp b ;compare lengths jr z,check_symbols, if they match, then compare the symbols ..... check_symbols inc hl; go to label symbols ld de,adr; address of the symbols of the searched label xor 15 ;15-a ldc,a add a,a add a,c ld c,#0f;restored c add a,a;a*6 ld(jmr+1),a jmr jr nz,$ ld a,(de) cp(hl) jr nz,oblom ;tags did not match, compare others inc e inc hl ... oblom let's start searching for the trace. tags. A few words about creating labels. As soon as the number of labels with one key exceeds the size allocated for pointers memory will open the next block of memory (possibly in a different page) for labels. Somewhat uneconomical, but the assembler was originally planned for computers with memory more than 128 kg. In my test, I used labels from the file with labels for Zasm3.10 (authors In their naivety, they thought that people would write overlays for their monster). The labels are all in capital letters. their length ranges from 2 to 11 characters. (Most the long label I used was 13 characters: GOPS_MUST_DIE ;) I hope no one was offended? ;)) DL> according to my estimates, 50...100 times for N=256. if I understand correctly, NDL> is directly related to the key bit depth, right? 2^(bit size)=N? And you get it right the first time ;). AM>> Perhaps, if I can do the calculations quickly, AM>> a search method with hashing based on the method will be introduced AM>> eliminating collisions of the Quadratic Sample name, DL> everything is clear ;) But I personally don’t really understand the method of this test, maybe you can explain? ;-))) AM>> P.S. Theoretically, the speed of assembly of commands like ldi, neg, cpl, AM>> nop will be no more than: on the first pass - 80 cycles/command. Look: lnbeg ld a,(hl) ; line length 7 inc hl ;13 dec a ;17 jr z,lnbeg;24 jp m,error;34. 7 bits of string length - a sign of a syntax error ld b,a ;38 ld a,(hl) ;46.the first thing in the line cp 15 ;52 jp nc,command1;62 ;processing of labels, directives like ".", "+", "-", comments command ld a,(hl) command1 inc hl ;68 cpopers;75 jr nc,n_operands;82 processing commands with operands exx;86 inc de;de-$;92 cp onebyte ;99 jr c,$+3; ;106 bypass if single-byte command inc de ;112 exx ;116 djnz command;124 next command separated by colonjp lnbeg ;134 total: 134 measures DL> will not work, you can trust me. realistically - about 200. Well, okay, 134 bars - I was bragging from memory ;) But if after a colon To write such commands, it will take about 70 cycles m/. AM>> on AM>> second pass - 160 clock cycles/command. DL> and in general - it should be one-pass ;) what is the second pass to the bathhouse? Yes, I have a hard time imagining how all sorts of forward references are made there, maybe throw in an idea. I wish you health, happiness and creative Uzbeks. Aleksey Malov aka VIVID/Brainwave.

Greetings, Dmitry! In principle, I will most likely store pointer blocks in the form of records, consisting of the following fields: 1 number of pointers to labels with a given key 2 array of m pointers. m= min (256, 4096/N), here N=2^(key capacity). 3 pointer (page and address) to the next entry with the same key. New a record will be created if the number of pointers in this record will exceed the size of the array in this entry. ┌───────────────────────────────┐ ┌─────┐ │number of pointers with key 0 │ │ │ ├───────────────────────────────┤ │ │ │pointers to marks ├────────>│ ├─────> ... └───────────────────────────────┘ └─────┘ ..... ┌───────────────────────────────┐ │number of pointers with key N-1 │ ├───────────────────────────────┤ │pointers to marks ├───────>.... └───────────────────────────────┘ I wish you health, happiness and creative Uzbeks. Aleksey Malov aka VIVID/Brainwave.

Hello, Alexey! One day, Mon Apr 03 2000 23:45, Aleksey Malov wrote to Dmitry Lomov about [Quick search using hashing.]: AM> Convenience in terms of interface (I don’t like Alasm because of this), AM> presence of local labels (useful thing), high speed (Zasm AM> infuriates), s ;) AM> and support for my 1Mb Simm (No one except Alasm above 128k AM> does not understand the route, but Alasm is not convenient). Well, in Storm only AM> multicolor screensaver is not enough ;). Hehe. AM> It is planned to store labels in tokenized form, because the following AM> character sequences: loop, LOOP, ER,er, bank,BANK, AND AM> T.P. occur quite often and save on memory and speed AM> search will increase slightly, and because of this it will turn out more or less AM> decent spread of keys. yeah, this is clearly overkill. no need to do that ;) Tokenization of tags is, of course, necessary, but not like that. DL>> the best option is to count the CRC of all letters of the label, perhaps DL>> including the length byte. option - CRC8, optimal polynomialDL>>calculated AM> Could you tell us more about the CRC calculation algorithm. Now I hardly remember my calculations and developments. but I have the following ready to go ;) ─ RU.ALGORITHMS (2:5030/255.27) ────────────────────────────── RU.ALGORITHMS ─ Post: 145 of 237 Scn From: Den Soroka 2:4641/121.256 10 Jan 99 21:40:00 To: Denis Korablev 14 Jan 99 02:27:46 Subject: CRC ─────────────────── ──────────────────── ──────────────────── ──────────────────── Good day Denis! Somehow Fri Jan 08 1999, DENIS KORABLEV trampled the keys for all!: DK> Sorry for the stupid question, but how to count the subject? 1. Let us be given a bit series 101110011... of length L bits. Let's imagine this series as a polynomial L-1 L-2 L-3 A=1* 2 + 0*2 + 1*2 + ... Now let's take any number less than L (1010) in length and imagine it similarly in the form of a polynomial B. Now let’s calculate the remainder when dividing A by B. This remainder will be an analogue of the CRC code. 101110011 | 1010 -1010------- ---- |100101 1100 -1010 ---- 1011 -1010 ---- 1<----remainder2. Now if instead of subtraction you use XOR then this will be a calculation real CRC code 101110011 | 1010 xor 1010 ------- ---- |100111 1100 xor 1010 ---- 1101 xor 1010 ---- 1111 xor 1010 ---- 101<----CRC code 3. XOR for each bit - very slow, so you can calculate it in advance code for each combination of n bits (in real algorithms n=8), for our example n=4. *** ---- pad n with zeros | 0001 0000 | 1010 1 010 ------- ---> 0001 corresponds to 0100 ----- | 00010 100 *** 0011 0000 | 1010 10 10 ------- ---> 0011 corresponds to 0110 ----- | 00111 1 100 1,010 ----- 1100 1010 ---- 110 *** Then we get 0001 0111 0011 | xor ----0100 x ----o 0011 r | ----0110 ---- 101<----- CRC code (coincides with the one already calculated, no matter how strange :) 4. Any number can be taken as number B, but there are numbers for which have been proven to provide the greatest likelihood error detection: CRC-16/CITT: 1021h XMODEM: 8408h ARC: 8005h CRC-32: 04C11DB7h 5. You can read in more detail and strictly on the Internet about ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txtDenis Soroka -+- + Origin: Den's Lair, Zaporozhye, Ukraine (FidoNet 2:4641/121.256) DL>> provide a detailed description of your method, and in return you will receive mine ;) AM> memory for tags is planned to be allocated as follows: AM> labels along with their values grow sequentially from top to bottom. AM> pointers to labels are located below: AM> [memory for m pointers to labels with key 0] AM> .... AM> [memory for m pointers to labels with key N-1] AM> m - power of two. oh how bad :( such a decision makes sense only when you have already made all other decisions has reached the theoretical speed limit, but you need more ;) in general, you should never make large fixed buffers, and even such a hole as yours. small buffers in your case - sax, it’s not clear, what to do if they overflow. STORM 1.3: a 256-word table that stores links to the first elements chains of labels that correspond to the same key (eight-bit). each label contains length, name, value, flags and a link to the next one a mark in the chain (or a sign at the end of the chain). AM> Search like this: AM> 1. Calculate the key for the required label using some algorithm. AM> 2. Next, look in a separate table to see how many pointers there are AM> to labels with this key. what for? It's easier to make an end marker. AM> 3. set sp to the beginning of the table AM> pointers to labels with this key. similarly, only I have this address in the table. AM> A few words about creating labels. AM> As soon as the number of labels with one key exceeds the size of the allocated under AM> memory pointers will open the next memory block (possibly in another AM> page) under the labels. Somewhat uneconomical, but the assembler is originally AM> was planned for computers with more than 128kb of memory. but I put such a fierce solution in storm2 ;) only there is much more more ferocious, the search is simply lightning fast. according to estimates - two to three times faster than you have :-) AM>>> P.S. Theoretically, the speed of assembly of commands like ldi, AM>>> neg, cpl, nop will be no more than: on the first pass - 80 AM>>> cycles/command. AM> See: AM> lnbeg ld a,(hl) ; line length 7 AM> inc hl ;13 AM> dec a ;17 AM> jr z,lnbeg;24 AM> jp m,error;34. 7 bits of string length - a sign of syntactic AM> errors length of the line at the beginning? But how are you going to go back through the text? ;) AM> ld b,a ;38 yeah, it's not the length of the line, it's the number of commands in the line? yes, memory for text you don't regret :-) losing a whole byte in a line for unjustified savings time is not best. AM> ld a,(hl) ;46.the first thing in the line AM> cp 15 ;52 AM> jp nc,command1;62 AM> ;processing of labels, directives like ".", "+", "-", comments AM> .... AM> command ld a,(hl) AM> command1 inc hl ;68 AM> cp opers;75 AM> jr nc,n_operands;82 processing commands with operands AM> exx;86 AM> inc de;de-$;92 AM> cp onebyte ;99 AM> jr c,$+3; ;106 bypass if single-byte command AM> inc de ;112 AM> exx ;116 AM> djnz command;124 next command separated by colon AM> jp lnbeg ;134 AM> total: 134 measures DL>> it won't work, you can trust me. realistically - about 200. AM> Well, okay, 134 bars - I was bragging from memory ;) But if after AM> colon to write such commands - then about 70 clock cycles will be m/. and generate the code? and the marks? I think "on average" :-) what if the jar runs out? what if the code buffer overflows? and if in memory instead text garbage? should I increase the number of the compiled line? and the number of the operand in the line increase? and for the second pass generate separate procedures that will do all this... yes, but is the text format strong? is everything reaped? how to navigate through the text editor will it be? I just worked on the text format for several months, taking into account the speed compilation and source volume... DL>> and in general - it should be one-pass ;) what, in the bathhouse, the second DL>> passage? AM> Yes, I have little idea how there are all sorts of forward links AM> are being done, maybe you can throw in an idea.I had such ferocious ideas that I could just hang myself... but some of them some had to be shot - one person will never write this. brain more resourceful than hands ;) in the general case, a list is maintained for expressions that are not currently evaluated, containing themselves, the place where the value should be written, and the method entering this value. Best wishes. Dmitry.

Greetings, All! So what do we have using hashing? It is easy to see that even with the most ideal method of calculating the hash function the maximum number of labels with the same key will be no less than C/(2^N), where C is the number of tags, N is the key bit size. In a real situation, this number is equal to approximately C/(2^(3*N/4)). Those. for 512 tags with N=8 this number will be about 8. For 1024 marks - 16. For 4096 - 64. If we use a tree, then what will be the search criterion? After all, we are looking for not numbers, but symbols of marks. If we represent label symbols as N-bit numbers, then the lion's share of time will be spent comparing 96-bit numbers (if the label length is no more than 16 characters and each character occupies 6 bits). B In the case of 512 labels, the weight of the tree will be no more than log 512 =9, i.e. with the number of marks less than 512 we lose to the hashing method. But already with the number of marks equal 1024 the number of search cycles will be 10. But when adding a new label it is necessary to ensure that the maximum difference in tree vertex levels was no more than 1. Otherwise, it is necessary to do balancing, i.e. throw pointers to vertices. In short, you need to come up with a search method that is realistic for the task at hand, and namely: 1. Adding tags occurs in random order, i.e. data comes in unsorted order. 2. Removing labels from the table is not required.3. It is not advisable to have more than 2 pointers attached to each label (memory must be saved). 4. Practical search speed should be high. 5. Everything will be implemented on the Spectrum in ASSEMBLY language. Therefore, to everyone algorithms that are more suitable for C and Pascal are better treated with caution. So offer your ideas (it is advisable that they be justified and satisfied the conditions of the task). At least there will be some benefit. This better than arguing about whether the C64 can use a floppy drive controller run several Amiga workbench's and at the same time play at speed 25 fps porn animations in MPEG format, downloaded in Real time from inet the help of a 2400 modem (if someone is still tormented by this question, then I will answer - won't be able to, even if Windows stops glitching, and Bill Gates bequeaths everything to me his fortune, and Slava Mednonogov will complete ChV-2 by the beginning of the Last Judgment). I wish you health, happiness and creative Uzbeks. Aleksey Malov aka VIVID/Brainwave.

Hello, Alexey! Once, Sat Apr 22 2000 00:25, Aleksey Malov wrote to Dmitry Lomov about [Quick search using hashing.]: DL>> but I put such a fierce solution in storm2 ;) only there DL>> is much more ferocious, the search is simply lightning fast. according to estimates - times in DL>> two or three faster than yours :-) AM> Maybe I can do it even faster ;)) it won't work ;) DL>> length of line at the beginning? but how will you go back through the text? DL>> ;) AM> Listen here: Each text on the page is no more than 16k and can consist of AM> of no more than 8192 lines. A small is stored along with the text. AM> a 64-byte plate containing row addresses, s AM> numbers divisible by 256. very difficult. but the idea itself is interesting. I didn't think of that before :) AM> [6] [LD] [A,B] [C,NUMBER] [DECIMAL BYTE] [7] AM> ^ AM> ║ AM> ║ AM> ╚═ string length AM> TOTAL: 6 BYTES per line. funny. my version matches this by 90% ;) AM> The text will occupy one jar (the number of texts will be limited AM> number of banks). bad. The expansion time of the 16k array is quite noticeable during operation. AM> Garbage will be checked simply - since we know the addresses AM> every 256 rows, it will not be difficult to compare the addresses in the tables with AM> addresses calculated by sequentially iterating over lines of text AM> after it is loaded or returned to assembler. add 100 bars per line ;) AM> Increment line number AM> no need for anything - in case of an error, I’ll just save the address of the erroneous line AM> in the error buffer. sound idea. Only then will you have to recalculate, but this is of little importance. AM> There is also no need - the text in memory will be stored in the form, maximum AM> chewed for assembler. if there are many commands in a line, you need to know which one is the error. however, by memorizing the address this is solved, however, after the slightest editing of the address text will move out. AM> metka push hl:adc hl,de:ret will look like: AM> [16] [simple label] [5] "metka" [push] [hl] [] [adc] [hl,de] [] [ret] AM> ^ AM> │ AM> │ AM> │ AM> └simple label [5] - length of the mark? it hurts so much ;) DL>> in the general case - for expressions that are not currently evaluated DL>> a list is maintained containing themselves, the place where it should be DL>> the value is written, and the method for entering this value. AM> This buffer will overflow very quickly. What, do you feel sorry for your memory? ;) Best wishes. Dmitry.