source: trunk/symtab/ls_symbol_table.cxx @ 4004

Last change on this file since 4004 was 1742, checked in by vla24, 7 years ago

SymbolTable?: Fixed custom hashing function for parallel bitstream based grouping

File size: 44.8 KB
Line 
1#include "ls_symbol_table.h"
2#include "ls_symbol_table_util.h"
3#define DEBUG 0
4#include <string>
5#include <iostream>
6#include "library_conversion.h"
7
8using namespace std;
9
10LSSymbolTable::LSSymbolTable(): crt_symbol_index_(0), crt_symbol_gid_(1) { // construct length bins 0,1,...32 and > 32
11
12        this->symbol_index_ = new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type)); // rows, columns, chunk size, alignment   
13       
14#ifdef USE_SYMBOL_PTRS 
15        this->symbol_value_ptrs_ = new HeapArray2D<unsigned char *> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type));
16#endif
17       
18#ifdef USE_SYMBOL_VALUES
19        this->symbol_values_ = new HeapArray2D<unsigned char>(LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type), sizeof(SIMD_type));
20#endif 
21       
22        this->uniq_symbol_values_ = new HeapArray2D<unsigned char> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type));
23        this->uniq_symbol_gids_ = new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type));
24
25#ifdef USE_LENGTH_SORT
26        this->gids_ = new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, 1);
27#endif 
28
29#ifdef USE_LENGTH_AND_KEY_SORT 
30        this->symbol_indices_.resize(LSSymbolTable::LGTH_BINS_);
31#endif 
32
33#ifdef USE_PACKED_SYMBOLS
34        this->uniq_key_packed_mask_splats_ = new HeapArray2D<SIMD_type> (1+8, 0, sizeof(SIMD_type)); // 8+1 rows, 0th length row + lengths 1 through 8
35        this->uniq_key_packed_gid_masks_ = new HeapArray2D<SIMD_type> (1+8, 0, sizeof(SIMD_type));
36        this->packed_gids_ = new HeapArray2D<uint32_t> (1+8, 0, 1);
37#endif         
38
39#ifdef USE_PARALLEL_TRIE
40        this->pfx_key_byte_splats_ = new HeapArray2D<SIMD_type> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type));     
41        this->pfx_index_splats_ = new HeapArray2D<SIMD_type> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type));   
42
43        this->unresolved_symbol_values_ = new HeapArray2D<unsigned char> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type));                     
44        this->unresolved_symbol_indices_= new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type)); 
45#endif 
46       
47        this->gid_idx_symbol_value_ptrs_ = new HeapArray<unsigned char *>();
48        this->gid_idx_symbol_lengths_ = new HeapArray<uint32_t>();
49        this->doc_idx_gids_ = new HeapArray<uint32_t>();
50}
51
52LSSymbolTable::~LSSymbolTable() {
53        delete this->symbol_index_;
54        this->symbol_index_ = NULL;
55       
56#ifdef USE_SYMBOL_PTRS 
57        delete this->symbol_value_ptrs_;
58        this->symbol_value_ptrs_ = NULL;
59#endif 
60       
61#ifdef USE_SYMBOL_VALUES
62        delete this->symbol_values_;
63        symbol_values_ = NULL;
64#endif 
65       
66        delete this->uniq_symbol_values_;
67        this->uniq_symbol_values_ = NULL;
68       
69        delete this->uniq_symbol_gids_;
70        this->uniq_symbol_gids_ = NULL;
71
72#ifdef USE_LENGTH_SORT
73        delete this->gids_;
74        this->gids_ = NULL;
75#endif 
76       
77#ifdef USE_PACKED_SYMBOLS
78        delete this->uniq_key_packed_mask_splats_;
79        this->uniq_key_packed_mask_splats_ = NULL;
80
81        delete this->uniq_key_packed_gid_masks_;
82        this->uniq_key_packed_gid_masks_ = NULL;
83
84        delete this->packed_gids_;
85        this->packed_gids_ = NULL;
86#endif         
87
88#ifdef USE_PARALLEL_TRIE
89        delete this->pfx_key_byte_splats_;
90        this->pfx_key_byte_splats_ = NULL;
91       
92        delete this->pfx_index_splats_;
93        this->pfx_index_splats_ = NULL;
94
95        delete this->unresolved_symbol_values_;
96        this->unresolved_symbol_values_ = NULL;
97       
98        delete this->unresolved_symbol_indices_;               
99        this->unresolved_symbol_indices_ = NULL;
100#endif         
101       
102        delete this->gid_idx_symbol_value_ptrs_;
103        this->gid_idx_symbol_value_ptrs_ = NULL;
104       
105        delete this->gid_idx_symbol_lengths_;
106        this->gid_idx_symbol_lengths_ = NULL;
107       
108        delete this->doc_idx_gids_;
109        this->doc_idx_gids_ = NULL;     
110}
111
112/*
113 * Note: All symbols of length >= 8 are sorted using symbol pointers and lengths.
114 */
115void LSSymbolTable::put(unsigned char * symbol_ptr, uint32_t lgth) {
116        if (lgth >= this->symbol_index_->rows()) {
117                uint32_t next_size = (lgth << 1); 
118
119                this->symbol_index_->reserve(next_size);
120
121#ifdef USE_SYMBOL_PTRS         
122                this->symbol_value_ptrs_->reserve(next_size);
123#endif
124               
125#ifdef USE_SYMBOL_VALUES
126                this->symbol_values_->reserve(next_size);
127#endif         
128               
129                this->uniq_symbol_values_->reserve(next_size);
130                this->uniq_symbol_gids_->reserve(next_size);
131               
132#ifdef USE_LENGTH_AND_KEY_SORT         
133                this->symbol_indices_.resize(next_size);
134#endif         
135       
136        }
137
138        this->symbol_index_->push_back(lgth, this->crt_symbol_index_);
139        this->crt_symbol_index_++;
140
141#ifdef USE_SYMBOL_PTRS 
142        this->symbol_value_ptrs_->push_back(lgth, symbol_ptr);
143#endif
144       
145#ifdef USE_SYMBOL_VALUES
146#ifdef USE_PACKED_SYMBOLS       
147        switch(lgth) {
148                case 1:
149                case 2:
150                case 4:
151                case 8:
152                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 0);
153                        break;
154                case 3:
155                case 7:
156                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 1);
157                        break;
158                case 5:
159                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 3);
160                        break;
161                case 6:
162                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 2);
163                        break;
164                default:
165                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 0);
166                        break;
167        }       
168#else   
169        this->symbol_values_->push_back(lgth, symbol_ptr, lgth);
170#endif
171#endif 
172
173}
174
175void LSSymbolTable::bind() {
176
177        this->doc_idx_gids_->resize(this->crt_symbol_index_);   // Resize the array to avoid unnecessary memory allocations.   
178       
179#ifndef USE_PARALLEL_TRIE       
180#ifdef USE_PACKED_SYMBOLS         
181        this->packed_gid_mask_128_ = simd<8>::constant<0>();
182
183        packed_bind<1>();
184        this->packed_gid_mask_128_ = simd_and(simd<fw<2>::value>::lomask(),
185                        this->packed_gid_mask_128_); // clear high half fw 16
186
187        packed_bind<2>();
188        this->packed_gid_mask_128_ = simd_and(simd<fw<4>::value>::lomask(),
189                        this->packed_gid_mask_128_); // clear high half fw 32
190
191        packed_bind<3>();
192        packed_bind<4>();
193        this->packed_gid_mask_128_ = simd_and(simd<fw<8>::value>::lomask(),
194                        this->packed_gid_mask_128_); // clear high half fw 64
195       
196        packed_bind<5>();
197        packed_bind<6>();
198        packed_bind<7>();
199        packed_bind<8>();
200
201        this->crt_symbol_gid_ = *((uint32_t *) (&this->packed_gid_mask_128_)); // glue packed symbols and non-packed symbols, i.e. convert the current gid to a non-packed gid value
202        this->crt_symbol_gid_++;
203#endif 
204       
205#ifdef USE_FUNCTION_OBJECTS
206#ifndef USE_PACKED_SYMBOLS       
207        bind<1,CmpS1>(cmpS1);
208        bind<2,CmpS2>(cmpS2);
209        bind<3,CmpS3>(cmpS3);
210        bind<4,CmpS4>(cmpS4);
211        bind<5,CmpS5>(cmpS5);
212        bind<6,CmpS6>(cmpS6);
213        bind<7,CmpS7>(cmpS7);
214        bind<8,CmpS8>(cmpS8);
215#endif
216        bind<9,CmpS9>(cmpS9);
217        bind<10,CmpS10>(cmpS10);
218        bind<11,CmpS11>(cmpS11);
219        bind<12,CmpS12>(cmpS12);
220        bind<13,CmpS13>(cmpS13);
221        bind<14,CmpS14>(cmpS14);
222        bind<15,CmpS15>(cmpS15);
223        bind<16,CmpS16>(cmpS16);
224        bind<17,CmpS17>(cmpS17);
225        bind<18,CmpS18>(cmpS18);
226        bind<19,CmpS19>(cmpS19);
227
228        bind<20,CmpS20>(cmpS20);
229        bind<21,CmpS21>(cmpS21);
230        bind<22,CmpS22>(cmpS22);
231        bind<23,CmpS23>(cmpS23);
232        bind<24,CmpS24>(cmpS24);
233        bind<25,CmpS25>(cmpS25);
234        bind<26,CmpS26>(cmpS26);
235        bind<27,CmpS27>(cmpS27);
236        bind<28,CmpS28>(cmpS28);
237        bind<29,CmpS29>(cmpS29);
238
239        bind<30,CmpS30>(cmpS30);
240        bind<31,CmpS31>(cmpS31);
241        bind<32,CmpS32>(cmpS32);
242#endif 
243       
244#ifdef USE_FUNCTION_TEMPLATES
245
246#ifndef USE_PACKED_SYMBOLS     
247        bind<1>();
248        bind<2>();
249        bind<3>();
250        bind<4>();
251        bind<5>();
252        bind<6>();
253        bind<7>();
254        bind<8>();
255        flatten_gids();
256#endif 
257        bind<9>();
258        bind<10>();
259        bind<11>();
260        bind<12>();
261        bind<13>();
262        bind<14>();
263        bind<15>();
264        bind<16>();
265//      bind<17>();
266//      bind<18>();
267//      bind<19>();
268
269//      bind<20>();
270//      bind<21>();
271//      bind<22>();
272//      bind<23>();
273//      bind<24>();
274//      bind<25>();
275//      bind<26>();
276//      bind<27>();
277//      bind<28>();
278//      bind<29>();
279
280//      bind<30>();
281//      bind<31>();
282//      bind<32>();
283#endif 
284#endif
285       
286#ifdef USE_PARALLEL_TRIE
287               
288        size_t unresolved_symbol_value_count;
289        // single byte prefix gather offsets
290        size_t offsets[sizeof(SIMD_type)];// = {0,L,2*L,3*L,4*L,5*L,6*L,7*L,8*L,9*L,10*L,11*L,12*L,13*L,14*L,15*L};
291               
292        // two byte prefix gather offsets
293        // unsigned char prefix_offsets[16] = {0,1,L,L+1,2*L,2*L+1,3*L,3*L+1,4*L,4*L+1,5*L,5*L+1,6*L,6*L+1,7*L,7*L+1};
294       
295        /*
296        ptrie_bind<1>();
297        ptrie_bind<2>();
298        ptrie_bind<3>();
299        ptrie_bind<4>();
300        ptrie_bind<5>();
301        ptrie_bind<6>();
302        ptrie_bind<7>();
303        ptrie_bind<8>();       
304        ptrie_bind<9>();
305        */
306        unresolved_symbol_value_count = this->symbol_values_->size(10)/10; 
307        prefix_offsets<10>(offsets);
308        ptrie_bind<10>(&this->symbol_values_->get(10,0), unresolved_symbol_value_count, offsets);
309       
310        /*
311        ptrie_bind<11>();
312        ptrie_bind<12>();
313        ptrie_bind<13>();
314        ptrie_bind<14>();
315        ptrie_bind<15>();
316        ptrie_bind<16>();
317        ptrie_bind<17>();
318        ptrie_bind<18>();
319        ptrie_bind<19>();
320
321        ptrie_bind<20>();
322        ptrie_bind<21>();
323        ptrie_bind<22>();
324        ptrie_bind<23>();
325        ptrie_bind<24>();
326        ptrie_bind<25>();
327        ptrie_bind<26>();
328        ptrie_bind<27>();
329        ptrie_bind<28>();
330        ptrie_bind<29>();
331
332        ptrie_bind<30>();
333        ptrie_bind<31>();
334        ptrie_bind<32>();
335        */     
336#endif                 
337       
338        /*bind_gt_32();*/ // bind all lengths > 32, this information is not known at compile time, and hence function call overhead and not inline template functions
339        bind_gt(17);
340        // TODO - flatten_gids may not be required.
341        // flatten_gids(); // flatten 2D length sorted gid values into a 1D document indexed array of GID values  TODO TBD.
342
343        this->symbol_index_->clear(); // clear 2D array of document indices
344
345#ifdef USE_LENGTH_SORT
346        this->gids_->clear(); // clear 2D parallel array of gid values
347#endif 
348
349#ifdef USE_SYMBOL_PTRS 
350        this->symbol_value_ptrs_->clear();
351#endif         
352       
353#ifdef USE_SYMBOL_VALUES
354        this->symbol_values_->clear();
355#endif 
356       
357#ifdef USE_PACKED_SYMBOLS
358        this->packed_gids_->clear();
359#endif
360
361#ifdef USE_LENGTH_AND_KEY_SORT 
362        for(size_t i=0;i<this->symbol_indices_.capacity();i++) {
363                for(size_t j=0;j<this->symbol_indices_[i].size();j++) {
364                        this->symbol_indices_[i][j].resize(0);
365                }
366        }
367#endif
368       
369}
370
371void LSSymbolTable::finalize() {
372        flatten_unique_symbol_values();
373        // TODO - Destroy temporary data structures. TBD.
374}
375 
376/*
377 * Description: Converts 2D length sorted unique symbols values to a pair of parallel 1D GID indexed parallel symbol pointer and length arrays.
378 *
379 * Note: To construct the GID indexed arrays, this method requires that unique symbols values are assigned GIDs inserted into the original 2D array
380 *       in order of increasing length and are assigned GIDs in order of new symbol occurrences.
381 *       
382 * Warning: Since pointers to unique symbol values are maintained in the 1D array, gid_idx_symbol_value_ptrs_ must only be destroyed
383 *          with the destruction of the complete Symbol Table object.     
384 *         
385 *          TODO - Consider the option of copying values from the 2D arrays into 1D arrays to allow for array clean up.
386 */
387void LSSymbolTable::flatten_unique_symbol_values() {
388
389        this->gid_idx_symbol_value_ptrs_->resize(this->crt_symbol_gid_-1);
390        this->gid_idx_symbol_lengths_->resize(this->crt_symbol_gid_-1);
391       
392        size_t symbol_index = 0;
393        for (size_t lgth = 0; lgth < this->uniq_symbol_values_->rows(); lgth++) { // for each length, for each unique symbol value pointer, store pointer and length 1D
394                for (size_t i = 0; i < this->uniq_symbol_values_->size(lgth); i += lgth) {
395//                      this->gid_idx_symbol_value_ptrs_->push_back(&this->uniq_symbol_values_->get(lgth, i));
396//                      this->gid_idx_symbol_lengths_->push_back(lgth);
397                        this->gid_idx_symbol_value_ptrs_->set(symbol_index,&this->uniq_symbol_values_->get(lgth, i)); 
398                        this->gid_idx_symbol_lengths_->set(symbol_index,lgth);
399                        symbol_index++;
400                }
401        }
402}
403
404/*
405 * Description: Essentially a scatter operation. Scatters 2D length sorted resolved GID values into a 1D document indexed array of gid values (unique numeric identifiers).   
406 */
407void LSSymbolTable::flatten_gids() {
408
409        uint32_t lgth = 0;
410        uint32_t next_gid = 0;
411       
412#ifdef USE_PACKED_SYMBOLS               
413        for (lgth; lgth < this->packed_gids_->rows(); lgth++) { // for each symbol of each length, for each GID in each GID pack, flatten into a 1D array of document gid values
414                for (size_t i = 0; i < this->packed_gids_->size(lgth); i++) {
415                        next_gid = this->packed_gids_->get(lgth, i);   
416                        this->doc_idx_gids_->set(this->symbol_index_->get(lgth, i),     next_gid);
417                }
418        }
419#endif
420
421/*
422TODO - Not required.
423
424#ifdef USE_LENGTH_SORT
425        for (lgth; lgth < this->gids_->rows(); lgth++) { // for each symbol of each length, glue gid values onto the 1D array of document indexed gid values
426                for (size_t i = 0; i < this->gids_->size(lgth); i++) {
427                        next_gid = this->gids_->get(lgth, i);           
428                        this->doc_idx_gids_->set(this->symbol_index_->get(lgth, i),     next_gid);
429                }
430        }
431#endif         
432*/
433
434#ifdef USE_LENGTH_AND_KEY_SORT 
435        for(lgth; lgth < this->symbol_indices_.size(); lgth++) { // for each key of length l
436                for(size_t i=0; i<this->symbol_indices_[lgth].size(); i++) {
437                        next_gid = this->uniq_symbol_gids_->get(lgth,i); // insert the gid at symbol index position
438                        for(size_t j=0; j<(this->symbol_indices_[lgth][i]).size();j++) {
439                                this->doc_idx_gids_->set((this->symbol_indices_[lgth][i][j]), next_gid);
440                        }
441                }
442        }
443#endif
444
445}
446
447/*
448 * Description: Sets size of all symbol table arrays to 0. No memory de-allocation is performed.
449 */
450void LSSymbolTable::clear() {
451
452        this->symbol_index_->clear();
453       
454        #ifdef USE_SYMBOL_PTRS 
455                this->symbol_value_ptrs_->clear();
456        #endif
457       
458        #ifdef USE_SYMBOL_VALUES
459                this->symbol_values_->clear();
460        #endif 
461       
462        this->uniq_symbol_values_->clear();
463        this->uniq_symbol_gids_->clear();
464
465#ifdef USE_LENGTH_SORT
466        this->gids_->clear();
467#endif         
468
469#ifdef USE_LENGTH_AND_KEY_SORT 
470        for(size_t i=0;i<this->symbol_indices_.capacity();i++) {
471                for(size_t j=0;j<this->symbol_indices_[i].size();j++) {
472                        this->symbol_indices_[i][j].clear();
473                }
474                this->symbol_indices_[i].clear();
475        }
476#endif
477
478#ifdef USE_PACKED_SYMBOLS
479        this->uniq_key_packed_mask_splats_->clear();
480        this->uniq_key_packed_gid_masks_->clear();
481        this->packed_gids_->clear();
482#endif         
483       
484        this->gid_idx_symbol_lengths_->clear();
485        this->gid_idx_symbol_value_ptrs_->clear();
486        this->doc_idx_gids_->clear();
487
488        this->crt_symbol_gid_ = 0;
489}
490
491void LSSymbolTable::display_lgth_dist() const {
492        cout << "display_lgth_dist()" << endl;
493
494#ifdef USE_LENGTH_SORT 
495        for (size_t lgth = 0; lgth < this->symbol_index_->rows(); lgth++) {
496                cout << "L[" << lgth << "]" << " => "
497                                << this->symbol_index_->size(lgth) << endl;
498        }
499#endif
500
501#ifdef USE_LENGTH_AND_KEY_SORT 
502        for(size_t lgth=0; lgth<this->symbol_indices_.capacity(); lgth++) {
503                cout << "L[" << lgth << "]" << " => " << this->symbol_index_->size(lgth) << endl;
504        }
505#endif
506
507        cout << endl;
508}
509
510void LSSymbolTable::display_flattened_symbol_values() const {
511        cout << "display_flattened_symbol_values()" << endl;
512
513        for (size_t i = 0; i < this->gid_idx_symbol_lengths_->size(); i++) {
514                cout << "GID[" << i << "] => " << string(
515                                (char *) (this->gid_idx_symbol_value_ptrs_->get(i)),
516                                this->gid_idx_symbol_lengths_->get(i)) << endl;
517        }
518
519        cout << endl;
520}
521
522void LSSymbolTable::display_flattened_gids() const {
523        cout << "display_flattened_gids()" << endl;
524        cout << "DOC_IDX_GID[] => ";
525
526        for (size_t i = 0; i < this->doc_idx_gids_->size(); i++) {
527                cout << this->doc_idx_gids_->get(i) << " ";
528        }
529        cout << endl;
530}
531
532vector<int> LSSymbolTable::get_flattened_gids()
533{
534    vector<int> gids;
535    for (size_t i = 0; i < this->doc_idx_gids_->size(); i++) {
536        int gid = this->doc_idx_gids_->get(i);
537        gids.push_back(gid);
538    }
539    return gids;
540}
541
542#ifdef USE_FUNCTION_OBJECTS
543
544template<uint32_t L, class Compare>
545inline void LSSymbolTable::bind(const Compare & compare) {
546
547        bool is_found;
548        uint32_t size;
549        uint32_t step;
550        bool is_equal;
551        unsigned char * uniq_key;
552               
553#ifdef USE_SYMBOL_PTRS 
554        size = this->symbol_value_ptrs_->size(L);
555        step = 1;
556#endif
557       
558#ifdef USE_SYMBOL_VALUES
559        size = this->symbol_values_->size(L);
560        step = L;
561#endif 
562       
563        for (size_t sym_val_idx = 0, sym_idx = 0; sym_val_idx < size; sym_val_idx+=step, sym_idx++) { // for each name of length L                     
564                is_found = false;
565                uint32_t uniq_symbol_value_bytes_ = this->uniq_symbol_values_->size(L);
566
567                uint32_t k = 0;
568                for (size_t j = 0; j < uniq_symbol_value_bytes_; j += L, k++) { // for each unique key name
569
570#ifdef USE_SYMBOL_PTRS                 
571                is_equal = compare(this->symbol_value_ptrs_->get(L,sym_val_idx), &this->uniq_symbol_values_->get(L,j));         
572#endif
573               
574#ifdef USE_SYMBOL_VALUES
575                is_equal = compare(&this->symbol_values_->get(L,sym_val_idx), &this->uniq_symbol_values_->get(L,j));
576#endif         
577                if(is_equal) {
578                               
579#ifdef USE_LENGTH_SORT         
580                                //this->gids_->push_back(L, this->uniq_symbol_gids_->get(L, k));
581                                this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx), this->uniq_symbol_gids_->get(L, k));                             
582#endif
583
584#ifdef USE_LENGTH_AND_KEY_SORT                         
585                                this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx)); // found, store symbol number
586#endif                         
587
588                                is_found = true;
589                                break;
590                        }
591                }
592
593                if (!is_found) { // not found, new unique key value
594                        // store new symbol value and gid value
595                        #ifdef USE_SYMBOL_PTRS                 
596                                uniq_key = this->symbol_value_ptrs_->get(L, sym_val_idx);
597                        #endif
598                               
599                        #ifdef USE_SYMBOL_VALUES
600                                uniq_key = &this->symbol_values_->get(L, sym_val_idx); 
601                        #endif
602                                       
603                        this->uniq_symbol_values_->push_back(L, uniq_key, L); // push a copy of the key value
604                        this->uniq_symbol_gids_->push_back(L, this->crt_symbol_gid_);
605
606#ifdef USE_LENGTH_SORT                         
607                        // this->gids_->push_back(L, this->crt_symbol_gid_);
608                        this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx), this->crt_symbol_gid_);                   
609#endif
610                        this->crt_symbol_gid_++;
611
612#ifdef USE_LENGTH_AND_KEY_SORT                 
613                        // allocate new symbol index vector
614                        vector <uint32_t> idxs;
615                        this->symbol_indices_[L].push_back(idxs);
616                        this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx));
617#endif                 
618                }
619        }       
620       
621}
622#endif 
623
624#ifdef USE_FUNCTION_TEMPLATES
625
626template<uint32_t L>
627inline void LSSymbolTable::bind() {
628        bool is_found;
629        uint32_t size;
630        uint32_t step;
631        bool is_equal;
632        unsigned char * uniq_key;
633               
634        #ifdef USE_SYMBOL_PTRS 
635                size = this->symbol_value_ptrs_->size(L);
636                step = 1;
637        #endif
638               
639        #ifdef USE_SYMBOL_VALUES
640                size = this->symbol_values_->size(L);
641                step = L;
642        #endif         
643
644        for (size_t sym_val_idx = 0, sym_idx = 0; sym_val_idx < size; sym_val_idx+=L, sym_idx++) { // for each name of length L
645
646                is_found = false;
647                uint32_t uniq_symbol_value_bytes_ = this->uniq_symbol_values_->size(L);
648
649                uint32_t k = 0;
650                for (size_t j = 0; j < uniq_symbol_value_bytes_; j += L, k++) { // for each unique key name
651
652#ifdef USE_SYMBOL_PTRS                 
653                is_equal = compare<L> (this->symbol_value_ptrs_->get(L, sym_val_idx), &this->uniq_symbol_values_->get(L, j));
654#endif
655               
656#ifdef USE_SYMBOL_VALUES
657                is_equal = compare<L> (&this->symbol_values_->get(L, sym_val_idx), &this->uniq_symbol_values_->get(L, j));
658#endif         
659                if(is_equal) {
660
661#ifdef USE_LENGTH_SORT                         
662                                // this->gids_->push_back(L, this->uniq_symbol_gids_->get(L, k));
663                            this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx),       this->uniq_symbol_gids_->get(L, k));
664                           
665#endif
666
667#ifdef USE_LENGTH_AND_KEY_SORT                         
668                                this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx)); // found, store symbol number
669#endif                         
670
671                                is_found = true;
672                                break;
673                        }
674                }
675
676                if (!is_found) { // not found, new unique key value
677                        // store new symbol value and gid value
678                        #ifdef USE_SYMBOL_PTRS 
679                                uniq_key = this->symbol_value_ptrs_->get(L, sym_val_idx); 
680                        #endif
681                               
682                        #ifdef USE_SYMBOL_VALUES
683                                uniq_key = &this->symbol_values_->get(L, sym_val_idx);
684                        #endif                         
685                       
686                        this->uniq_symbol_values_->push_back(L, uniq_key, L);
687                        this->uniq_symbol_gids_->push_back(L, this->crt_symbol_gid_);
688
689#ifdef USE_LENGTH_SORT                         
690                        //this->gids_->push_back(L, this->crt_symbol_gid_);
691                        this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx), this->crt_symbol_gid_);                   
692#endif
693                        this->crt_symbol_gid_++;
694
695#ifdef USE_LENGTH_AND_KEY_SORT                 
696                        // allocate new symbol index vector
697                        vector <uint32_t> idxs;
698                        this->symbol_indices_[L].push_back(idxs);
699                        this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx));
700#endif                 
701                }
702        }
703}
704
705#endif
706
707//Sort arrays of length 33 or greater
708void LSSymbolTable::bind_gt(int max_lgth) {
709
710        bool is_found;
711        uint32_t size;
712        uint32_t step;
713        bool is_equal;
714        unsigned char * uniq_key;       
715
716        for (size_t lgth = max_lgth+1; lgth < this->symbol_index_->rows(); lgth++) { // for each length >= 33
717
718                #ifdef USE_SYMBOL_PTRS 
719                        size = this->symbol_value_ptrs_->size(lgth);
720                        step = 1;
721                #endif
722                       
723                #ifdef USE_SYMBOL_VALUES
724                        size = this->symbol_values_->size(lgth);
725                        step = lgth;
726                #endif                 
727               
728                for (size_t sym_val_idx = 0, sym_idx = 0; sym_val_idx < size; sym_val_idx+=step, sym_idx++) { // for each unique key name
729               
730                        is_found = false;
731                        uint32_t uniq_symbol_value_bytes_ =     this->uniq_symbol_values_->size(lgth);
732
733                        uint32_t k = 0;
734                        for (size_t j = 0; j < uniq_symbol_value_bytes_; j += lgth, k++) { // for each unique key name
735
736                                #ifdef USE_SYMBOL_PTRS 
737                                        is_equal = simd_compare(this->symbol_value_ptrs_->get(lgth, sym_val_idx), &this->uniq_symbol_values_->get(lgth, j), lgth); 
738                                        //is_equal = mem_compare(this->symbol_value_ptr_[lgth][i], this->uniq_symbol_values_[lgth][j], lgth);
739                                #endif
740                                       
741                                #ifdef USE_SYMBOL_VALUES
742                                        is_equal = simd_compare(&this->symbol_values_->get(lgth, sym_val_idx), &this->uniq_symbol_values_->get(lgth, j), lgth);
743                                #endif                                                 
744                               
745                                if (is_equal) {
746
747#ifdef USE_LENGTH_SORT                         
748                                        // this->gids_->push_back(lgth, this->uniq_symbol_gids_->get(lgth, k));
749                                        this->doc_idx_gids_->set(this->symbol_index_->get(lgth, sym_idx), this->uniq_symbol_gids_->get(lgth, k));
750
751#endif
752
753#if USE_LENGTH_AND_KEY_SORT                                     
754                                        this->symbol_indices_[lgth][k].push_back(this->symbol_index_->get(lgth,sym_val_idx)); // found, store symbol number
755#endif
756                                        is_found = true;
757                                        break;
758                                }
759                        }
760
761                        if (!is_found) { // not found, new unique key value
762                                // store new unique key value and parallel gid value
763                                #ifdef USE_SYMBOL_PTRS 
764                                        uniq_key = this->symbol_value_ptrs_->get(lgth, sym_val_idx); 
765                                #endif
766                                       
767                                #ifdef USE_SYMBOL_VALUES
768                                        uniq_key = &this->symbol_values_->get(lgth, sym_val_idx);
769                                #endif 
770                               
771                                this->uniq_symbol_values_->push_back(lgth, uniq_key, lgth);
772                                this->uniq_symbol_gids_->push_back(lgth, this->crt_symbol_gid_);
773#ifdef USE_LENGTH_SORT                         
774                                //this->gids_->push_back(lgth, this->crt_symbol_gid_);
775                                this->doc_idx_gids_->set(this->symbol_index_->get(lgth,sym_idx), this->crt_symbol_gid_);
776#endif                         
777                                this->crt_symbol_gid_++;
778#if USE_LENGTH_AND_KEY_SORT                             
779                                // allocate new symbol index vector
780                                vector <uint32_t> idxs;
781                                this->symbol_indices_[lgth].push_back(idxs);
782                                this->symbol_indices_[lgth][k].push_back(this->symbol_index_->get(lgth,sym_val_idx));
783#endif                         
784                        }
785                }
786        }
787}
788
789#ifdef USE_PACKED_SYMBOLS // Short symbol optimization
790/*
791 * Note: Full packs and partial packs are placed in separate loops for two reasons: the logic is clearer and conditional branches are slightly less.
792 */
793template<uint32_t L>
794void LSSymbolTable::packed_bind() {
795        uint32_t pack_count = SYMBOL_PACK_COUNT[L];                                                             // symbols per SIMD register
796       
797        uint32_t symbol_count = 0;
798        uint32_t non_packed_symbol_count = 0;
799        uint32_t packed_symbol_count = 0;
800       
801        #ifdef USE_SYMBOL_PTRS
802                symbol_count = this->symbol_value_ptrs_->size(L);
803                non_packed_symbol_count = symbol_count & (pack_count - 1);     
804                packed_symbol_count = symbol_count - non_packed_symbol_count;
805        #endif
806               
807        #ifdef USE_SYMBOL_VALUES
808                symbol_count = this->symbol_values_->size(L)/SYMBOL_BYTES[L];
809                non_packed_symbol_count = symbol_count & (pack_count - 1);     
810                packed_symbol_count = symbol_count - non_packed_symbol_count;
811        #endif 
812                               
813        uint16_t exit_cond_mask_16 = 0xFFFF;
814        uint16_t done_mask_16 = 0;
815
816        SIMD_type result_gid = simd<1>::constant<0>();
817        SIMD_type crt_gid_mask_128 = simd<1>::constant<0>();
818        SIMD_type cmp_eq_mask_128 = simd<1>::constant<0>();
819
820        SIMD_type crt_uniq_key_mask_splat_128 = simd<1>::constant<0>();
821        SIMD_type key_mask_splat_128 = simd<1>::constant<0>();
822
823        SIMD_type crt_symbol_pack;
824        uint32_t uniq_key_mask_splats_index = 0;
825
826        /*
827         * Splat an initial key mask and gid pack.
828         */
829        if (symbol_count > 0) {
830                               
831                #ifdef USE_SYMBOL_PTRS
832                        key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) this->symbol_value_ptrs_->get(L, 0));         
833                #endif
834                       
835                #ifdef USE_SYMBOL_VALUES
836                        key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) &this->symbol_values_->get(L, 0));           
837                #endif                 
838                                       
839                uniq_key_packed_mask_splats_->push_back(L, key_mask_splat_128);
840                packed_gid_mask_128_ = inc<fw<L>::value> (packed_gid_mask_128_);
841                uniq_key_packed_gid_masks_->push_back(L, packed_gid_mask_128_);
842               
843                #ifdef USE_SYMBOL_PTRS
844                        this->uniq_symbol_values_->push_back(L, this->symbol_value_ptrs_->get(L, 0), L); // push_back an address makes copy of the value
845                #endif 
846                       
847                #ifdef USE_SYMBOL_VALUES
848                        this->uniq_symbol_values_->push_back(L,&this->symbol_values_->get(L,0),L);               // push_back an address makes copy of the value
849                #endif                 
850        }
851
852        /*
853         * Full symbol packs.
854         */     
855        size_t sym_idx=0;
856        size_t sym_val_idx=0;                                                                   // symbol index
857        size_t step=0;
858        size_t limit = 0;
859        size_t next_gid=0;
860
861        #ifdef USE_SYMBOL_PTRS 
862                step = pack_count;
863                limit = packed_symbol_count;                    // full SIMD packs in terms of symbol bytes rounded up to the next power of 2
864        #endif
865       
866        #ifdef USE_SYMBOL_VALUES
867                step = sizeof(SIMD_type);
868                limit = packed_symbol_count * SYMBOL_BYTES[L];          // full SIMD packs in terms of bytes, step sizeof(SIMD_type) bytes at a time
869        #endif
870       
871        for(sym_val_idx=0;sym_val_idx<limit;sym_val_idx+=step) { 
872               
873                #ifdef USE_SYMBOL_PTRS
874                        crt_symbol_pack = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, sym_val_idx))); // set next symbol pack
875                #endif
876                       
877                #ifdef USE_SYMBOL_VALUES
878                        crt_symbol_pack = sisd_load_aligned((SIMD_type *)&this->symbol_values_->get(L,sym_val_idx));   
879                #endif 
880                       
881                cmp_eq_mask_128 = simd<1>::constant<0>();
882                done_mask_16 = 0;
883                uniq_key_mask_splats_index = 0;
884
885                while (1) { // compare a 'symbol pack' of symbols until all symbols in the pack are matched
886
887                        crt_uniq_key_mask_splat_128 = uniq_key_packed_mask_splats_->get(L, uniq_key_mask_splats_index); // get next SIMD key splat
888                        crt_gid_mask_128 = uniq_key_packed_gid_masks_->get(L, uniq_key_mask_splats_index);                              // get parallel gid splat 
889
890#ifdef USE_SIMD_AND
891                        cmp_eq_mask_128 = simd<fw<L>::value>::eq(crt_symbol_pack, crt_uniq_key_mask_splat_128);                 // SIMD compare value against key splat
892#endif                 
893
894#ifdef USE_SSE_4_2     
895                        cmp_eq_mask_128 = _mm_cmpestrm(crt_uniq_key_mask_splat_128, L, crt_symbol_pack, sizeof(SIMD_type), _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_UNIT_MASK);
896                        cmp_eq_mask_128 = umask_2_smask<fw<L>::value>(cmp_eq_mask_128);
897#endif
898
899                        result_gid = simd_or(result_gid, simd_and(cmp_eq_mask_128, crt_gid_mask_128));
900                        done_mask_16 |= hsimd<8>::signmask(cmp_eq_mask_128);
901
902#ifdef SYMBOL_TABLE_DEBUG
903                        print_simd_register("Symbol Pack", crt_symbol_pack);
904                        print_simd_register("Key Splat", crt_uniq_key_mask_splat_128);
905                        print_simd_register("Symbols AND Keys", cmp_eq_mask_128);
906                        print_simd_register("GID Mask", crt_gid_mask_128);
907                        print_simd_register("GIDs OR (Symbols AND Keys)", result_gid);
908                        print_general_register_32("Done Mask (16 bit)", done_mask_16);
909                        print_general_register_32("Exit Mask (16 bit)", exit_cond_mask_16);
910                        cout << endl;
911#endif
912
913                        if (exit_cond_mask_16 == done_mask_16) {
914
915                                if(DEBUG)cout << "L " << L << " pack_count " << pack_count << endl;
916                               
917                                // Set gids
918                                for(size_t gid_idx=0, simd_register_offset=0; gid_idx < pack_count; gid_idx++, simd_register_offset+=(bin<L>::value)) {
919                                        next_gid = (size_t) *((( (unsigned char *) &result_gid) )+simd_register_offset);
920                                        this->doc_idx_gids_->set(this->symbol_index_->get(L, sym_idx), next_gid);
921                                        sym_idx++;
922                                }
923
924                                result_gid = simd<1>::constant<0>();    // clear gid pack
925                                break;
926                        }
927
928                        if ((++uniq_key_mask_splats_index) == uniq_key_packed_mask_splats_->size(L)) { // add a new unique key and gid masks
929                                uint32_t i = bsf(~done_mask_16); // find 'pointer arithmetic' offset to a symbol yet to be matched
930                                crt_uniq_key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) (&crt_symbol_pack) + i); //gather/splat a new unique key mask
931
932#ifdef SYMBOL_TABLE_DEBUG
933                                print_simd_register("New Key Mask", crt_uniq_key_mask_splat_128);
934                                print_simd_register("New GID Mask", packed_gid_mask_128_);
935#endif
936                                uniq_key_packed_mask_splats_->push_back(L, crt_uniq_key_mask_splat_128);
937                                packed_gid_mask_128_ = inc<fw<L>::value> (packed_gid_mask_128_);
938                                uniq_key_packed_gid_masks_->push_back(L, packed_gid_mask_128_);
939                               
940                                this->uniq_symbol_values_->push_back(L, (const unsigned char *) (&crt_symbol_pack) + i, L); // this index does not track the array positions, it tracks the register position
941                        }
942                }
943        }
944
945        /*
946         * Partial symbol packs.
947         */                     
948        if(non_packed_symbol_count != 0) {
949
950                cmp_eq_mask_128 = simd<1>::constant<0>();
951                done_mask_16 = 0;
952                uniq_key_mask_splats_index = 0;
953               
954                #ifdef USE_SYMBOL_PTRS
955                        crt_symbol_pack = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, sym_val_idx)), non_packed_symbol_count); // set next symbol pack
956                #endif
957                       
958                #ifdef USE_SYMBOL_VALUES
959                        crt_symbol_pack = sisd_load_aligned((SIMD_type *)&this->symbol_values_->get(L,sym_val_idx));   
960                #endif                 
961               
962                uint32_t mask_bits = (sizeof(SIMD_type) / pack_count) * (non_packed_symbol_count);
963                exit_cond_mask_16 = 1; 
964                exit_cond_mask_16 <<= mask_bits;
965                exit_cond_mask_16 -= 1;
966                       
967                while(1) {
968
969                        crt_uniq_key_mask_splat_128 = uniq_key_packed_mask_splats_->get(L, uniq_key_mask_splats_index); // get next SIMD key splat
970                        crt_gid_mask_128 = uniq_key_packed_gid_masks_->get(L, uniq_key_mask_splats_index); // get parallel gid splat 
971
972#ifdef USE_SIMD_AND
973                        cmp_eq_mask_128 = simd<fw<L>::value>::eq(crt_symbol_pack, crt_uniq_key_mask_splat_128); // SIMD compare value against key splat
974#ifdef SYMBOL_TABLE_DEBUG
975                        print_simd_register("cmp_eq_mask_128", cmp_eq_mask_128);
976#endif                 
977#endif                 
978
979#ifdef USE_SSE_4_2     
980                        cmp_eq_mask_128 = _mm_cmpestrm(crt_uniq_key_mask_splat_128, L, crt_symbol_pack, sizeof(SIMD_type), _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_UNIT_MASK);
981                        cmp_eq_mask_128 = umask_2_smask<fw<L>::value>(cmp_eq_mask_128);
982#ifdef SYMBOL_TABLE_DEBUG
983                        print_simd_register("cmp_eq_mask_128",cmp_eq_mask_128);
984#endif                 
985#endif
986                        result_gid = simd_or(result_gid, simd_and(cmp_eq_mask_128, crt_gid_mask_128));
987                        done_mask_16 |= hsimd<8>::signmask(cmp_eq_mask_128);
988                                               
989                        if(exit_cond_mask_16 == done_mask_16) {
990
991                                for(size_t gid_idx=0, crt_sym_idx=sym_idx, simd_register_offset=0; gid_idx < non_packed_symbol_count; gid_idx++, crt_sym_idx++, simd_register_offset+=(bin<L>::value)) {
992                                        next_gid = (size_t) *((( (unsigned char *) &result_gid) )+simd_register_offset);
993                                        this->doc_idx_gids_->set(this->symbol_index_->get(L, crt_sym_idx), next_gid);
994                                }
995                                break;
996                        }
997
998                        if ((++uniq_key_mask_splats_index) == uniq_key_packed_mask_splats_->size(L)) { // add a new unique key and gid masks
999                                uint32_t i = bsf(~done_mask_16); // find 'pointer arithmetic' offset to a symbol yet to be matched
1000                                crt_uniq_key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) (&crt_symbol_pack) + i); //gather/splat a new unique key mask
1001
1002#ifdef SYMBOL_TABLE_DEBUG
1003                                print_general_register_32("Done Mask (16 bit)", done_mask_16);
1004                                print_simd_register("Next Key Mask", crt_uniq_key_mask_splat_128);
1005                                print_simd_register("Next GID Mask", packed_gid_mask_128_);
1006#endif
1007                                uniq_key_packed_mask_splats_->push_back(L, crt_uniq_key_mask_splat_128);
1008                                packed_gid_mask_128_ = inc<fw<L>::value> (packed_gid_mask_128_);
1009                                uniq_key_packed_gid_masks_->push_back(L, packed_gid_mask_128_);
1010                               
1011                                this->uniq_symbol_values_->push_back(L, (const unsigned char *) (&crt_symbol_pack) + i, L); // this index does not track the array positions, it tracks the register position
1012                        }                                               
1013                }       
1014        }       
1015}
1016
1017#endif
1018
1019#ifdef USE_SYMBOL_VALUES       
1020#ifdef USE_PARALLEL_TRIE
1021
1022// NO NEED TO PASS IN THE UNRESOLVED SYMBOL COUNT
1023
1024template<uint32_t L>
1025void LSSymbolTable::prefix_offsets(size_t * prefix_offsets) {
1026        for(size_t i=0;i<sizeof(SIMD_type);i++) {
1027                prefix_offsets[i] = 10*i;
1028        }
1029}
1030
1031template<uint32_t L>
1032void LSSymbolTable::ptrie_bind(const unsigned char * symbol_values, size_t unresolved_symbol_count, size_t * offsets) {
1033       
1034        const uint32_t N = 1;                                                                                           // number of prefix bytes
1035        uint32_t non_packed_symbol_count = 0;
1036        uint32_t packed_symbol_count = 0;               
1037       
1038        non_packed_symbol_count = unresolved_symbol_count & (N-1);                      // number of prefix bytes must be a power of 2
1039        packed_symbol_count = unresolved_symbol_count - non_packed_symbol_count;
1040       
1041        SIMD_type crt_pfx_key_byte_splats_128 = simd<1>::constant<0>();         // current iteration values
1042        SIMD_type crt_pfx_index_splats_128 = simd<1>::constant<0>();            // current iteration values
1043        SIMD_type cmp_eq_mask_128 = simd<1>::constant<0>();                                     // comparison accumulator
1044        SIMD_type rslt_pfx_index_splats_128 = simd<1>::constant<0>();           // prefix index accumulator
1045       
1046        uint32_t prefix_key_byte_splats_index = 0;                                                      // next index value
1047       
1048        /*
1049         * Splat a SIMD register of prefix key bytes and
1050         * splat a SIMD register of unresolved symbol value indices.
1051         */
1052        if (unresolved_symbol_count > 0) {
1053                                                       
1054                crt_pfx_key_byte_splats_128 = simd<fw<N>::value>::splat(*(SIMD_type *) &this->symbol_values_->get(L, 0));               
1055                this->pfx_key_byte_splats_->push_back(L, crt_pfx_key_byte_splats_128);
1056                crt_pfx_index_splats_128 = inc<fw<N>::value> (crt_pfx_index_splats_128);
1057                this->pfx_index_splats_->push_back(L,crt_pfx_index_splats_128);
1058
1059                print_simd_register("crt_pfx_key_byte_splats_128", crt_pfx_key_byte_splats_128);
1060                print_simd_register("crt_pfx_index_splats_128", crt_pfx_index_splats_128);
1061
1062        }
1063               
1064        /*
1065         * Full symbol packs.
1066         */     
1067        size_t i = 0;                                                   
1068        size_t step = 0;
1069        size_t limit = 0;       
1070       
1071        step = sizeof(SIMD_type);
1072        limit = packed_symbol_count;                                                                                    // step w.r.t. number of bytes, i.e. sizeof(SIMD_type) bytes at a time
1073               
1074        unsigned char * base_addr = NULL;
1075
1076        uint16_t exit_cond_mask_16 = 0xFFFF;                                                                    // full pack exit condition value
1077        uint16_t done_mask_16 = 0;                                                                                              // current termination value   
1078               
1079        SIMD_type crt_prefix_pack_128;
1080        for(i=0;i<limit;i+=step) {
1081
1082                cmp_eq_mask_128 = simd<1>::constant<0>();
1083                done_mask_16 = 0;
1084                prefix_key_byte_splats_index = 0;                                                                               // loop index variable
1085               
1086                base_addr = &this->symbol_values_->get(L,i);                                                    // get next base address for parallel gather
1087                crt_prefix_pack_128 = simd<8>::gather(base_addr, offsets, SF1);                 // get next N byte prefix pack based on prefix_index values
1088                               
1089                print_simd_register("crt_prefix_pack",crt_prefix_pack_128);
1090               
1091                while(1) {      // SIMD compare and scatter input symbols to arrays of symbols with common prefix values
1092               
1093                        crt_pfx_key_byte_splats_128 = this->pfx_key_byte_splats_->get(L, prefix_key_byte_splats_index); 
1094                        crt_pfx_index_splats_128 = this->pfx_index_splats_->get(L, prefix_key_byte_splats_index);
1095                       
1096                        print_simd_register("crt_prefix_pack",crt_prefix_pack_128);
1097                        print_simd_register("crt_pfx_key_byte_splats_128",crt_pfx_key_byte_splats_128);
1098                        print_simd_register("crt_pfx_index_splats_128",crt_pfx_index_splats_128);
1099                                               
1100                        #ifdef USE_SIMD_AND
1101                                cmp_eq_mask_128 = simd<fw<N>::value>::eq(crt_prefix_pack_128, crt_pfx_key_byte_splats_128); 
1102                                #ifdef SYMBOL_TABLE_DEBUG
1103                                        print_simd_register("cmp_eq_mask_128", cmp_eq_mask_128);
1104                                #endif                 
1105                        #endif                 
1106               
1107                        #ifdef USE_SSE_4_2     
1108                                cmp_eq_mask_128 = _mm_cmpestrm(crt_pfx_key_byte_splats_128, L, crt_pfx_index_splats_128, sizeof(SIMD_type), _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_UNIT_MASK);
1109                                cmp_eq_mask_128 = umask_2_smask<fw<L>::value>(cmp_eq_mask_128);
1110                                #ifdef SYMBOL_TABLE_DEBUG
1111                                        print_simd_register("cmp_eq_mask_128",cmp_eq_mask_128);
1112                                #endif                 
1113                        #endif
1114
1115                        rslt_pfx_index_splats_128 = simd_or(rslt_pfx_index_splats_128, simd_and(cmp_eq_mask_128, crt_pfx_index_splats_128));
1116                        done_mask_16 |= simd<8>::movemask(cmp_eq_mask_128);                                             
1117                                               
1118                        if(exit_cond_mask_16 == done_mask_16) { // distribute symbol value copies to 2D array bins based on prefix bytes
1119                               
1120                                print_simd_register("rslt_pfx_index_splats_128",rslt_pfx_index_splats_128);                                                             
1121                                uint16_t unresolved_symbols_idx;
1122
1123                                // for each prefix, copy the symbol index and symbol value to parallel 'unresolved symbol index' and 'unresolved symbol value' arrays
1124                                for(int simd_prefix_register_index=0,symbol_value_index=0,global_symbol_index=0;simd_prefix_register_index<sizeof(SIMD_type);simd_prefix_register_index+=N,symbol_value_index+=L,global_symbol_index++) {
1125                                       
1126                                        // TODO - Template specialization on N (number of prefix bytes)
1127                                        unresolved_symbols_idx = *((uint8_t *) (((uint8_t *)&rslt_pfx_index_splats_128) + simd_prefix_register_index));
1128                                        // unresolved_symbols_idx = *((uint16_t *) (((uint8_t *)&rslt_pfx_index_splats_128) + pfx_register_index));
1129       
1130                                        this->unresolved_symbol_indices_->push_back(unresolved_symbols_idx, this->symbol_index_->get(L,global_symbol_index));
1131                                        this->unresolved_symbol_values_->push_back(unresolved_symbols_idx, &symbol_values[symbol_value_index], L);             
1132                                }
1133                                cout << endl;
1134                               
1135                                #ifdef SYMBOL_TABLE_DEBUG
1136                                size_t cols;
1137                                for(int row=0;row<this->unresolved_symbol_values_->rows();row++) {
1138                                        cols = this->unresolved_symbol_values_->size(row);
1139                                        cout << "cols " << cols << endl;
1140                                        for(int col=0;col<cols;col+=L) {
1141                                                cout << string((char *) &this->unresolved_symbol_values_->get(row, col),L) << endl;
1142                                        }
1143                                }
1144                                cout << endl;
1145                                #endif
1146                               
1147                                break;
1148                        }
1149
1150                        printf("%d,%d\n",prefix_key_byte_splats_index,this->pfx_key_byte_splats_->size(L));
1151                       
1152                        if ((++prefix_key_byte_splats_index) == this->pfx_key_byte_splats_->size(L)) { // add a new unique key and gid masks
1153                               
1154                                uint32_t i = bsf(~done_mask_16); // find 'pointer arithmetic' offset to a symbol yet to be matched                                                                     
1155                                crt_pfx_key_byte_splats_128 = simd<fw<N>::value>::splat ((unsigned char *) (&crt_prefix_pack_128) + i); //gather/splat a new unique key mask
1156                       
1157                                this->pfx_key_byte_splats_->push_back(L, crt_pfx_key_byte_splats_128);
1158                                crt_pfx_index_splats_128 = inc<fw<N>::value> (crt_pfx_index_splats_128);
1159                                this->pfx_index_splats_->push_back(L,crt_pfx_index_splats_128);                         
1160
1161                                print_simd_register("crt_prefix_pack",crt_prefix_pack_128);
1162                                print_simd_register("crt_pfx_key_byte_splats_128",crt_pfx_key_byte_splats_128);
1163                                print_simd_register("crt_pfx_index_splats_128",crt_pfx_index_splats_128);                               
1164                               
1165                        }                               
1166                }               
1167        }
1168       
1169        /*
1170         * Resolve current Trie level, full match prefix sorted values
1171         */     
1172        bool is_equal;
1173       
1174        int cols = 0;
1175        int copy_to_index = 0;
1176       
1177        unsigned char * search_key_value;
1178        uint32_t crt_gid;
1179       
1180        size_t symbol_value_bytes;
1181        for(int row=0;row<this->unresolved_symbol_values_->rows();row++) {
1182               
1183                cout << this->unresolved_symbol_values_->size(row) << endl;
1184               
1185                search_key_value = &this->unresolved_symbol_values_->get(row, 0);                                                                                                       // parallel search key and gid values
1186                this->crt_symbol_gid_++;
1187                crt_gid = this->crt_symbol_gid_;
1188               
1189                this->uniq_symbol_values_->push_back(L, search_key_value, this->uniq_symbol_values_->size());                                           // save a copy of the key value and gid value
1190                this->uniq_symbol_gids_->push_back(L, this->crt_symbol_gid_);
1191               
1192                copy_to_index = 0;
1193                symbol_value_bytes = this->unresolved_symbol_values_->size(row);
1194               
1195                for(size_t global_symbol_index=0, symbol_value_index=0; symbol_value_index<symbol_value_bytes; global_symbol_index++, symbol_value_index+=L) {                                 
1196                                                       
1197                        cout << string((char *)search_key_value,L) << endl;
1198                        cout << string((char *)&this->unresolved_symbol_values_->get(row,symbol_value_index),L) << endl;
1199                       
1200                        is_equal = compare<L>(&this->unresolved_symbol_values_->get(row,symbol_value_index), search_key_value);
1201                       
1202                        if(is_equal) { // set the global symbol numeric identifier value, bind gid to symbol
1203                                this->doc_idx_gids_->set(this->unresolved_symbol_indices_->get(row, global_symbol_index), crt_gid);
1204                        } else {
1205                                // THIS VALUE NEEDS TO BE THE UNRESOLVED SYMBOLS PASSED TO THE NEXT LEVEL OF THE TRIE
1206                                //this->unresolved_symbol_values_->set(row, copy_to_index, search_key_value, L);
1207                                copy_to_index += L;
1208                        } 
1209                }
1210        }
1211               
1212        display_flattened_gids();
1213/*
1214    // Resolve current TRIE level
1215
1216    for i=0 to uniq_key_values_.size() {
1217
1218      key_value = ptrie_partial_match_values_[0]
1219
1220      // Get next partial match value AND based on this partial match value add ...
1221      // Add a new unique value AND add a new parallel GID value
1222
1223      crt_value = this->uniq_symbol_values_.get(L,i);
1224      crt_gid = this->uniq_symbol_gids_.get(L,i);
1225
1226      for(i=0 to ptrie_partial_match_values.size()) {
1227
1228        if(key == ptrie_partial_match_values_[i]) {
1229          // Bind symbol at 'symbol_index_' to a unique numeric identifier
1230
1231          // Set GID array value (gid_) at this index value
1232
1233          this->gids_.set(L,this->crt_symbol_index_.get(L,i);
1234
1235         
1236        } else {
1237          // Append the value to 'unresolved' symbols arrays AND
1238          // Append the symbol index value to the parallel index array
1239        }
1240      }
1241
1242      PTrie<L>(unresolved_symbol_index_array, symbol_count)
1243      unresolved_symbol_index_array.clear()
1244    }
1245
1246    // ptrie_partial_match_values_.clear()
1247 */     
1248       
1249        exit(1);
1250}
1251
1252#endif
1253#endif
1254
1255#ifdef USE_PACKED_SYMBOLS
1256
1257template<>
1258inline void LSSymbolTable::push_gid<1>(const SIMD_type value, const uint32_t count) {
1259
1260        SIMD_type lo, hi;
1261
1262        lo = esimd<fw<1>::value>::mergel(simd<1>::constant<0>(), value);
1263        hi = esimd<fw<1>::value>::mergeh(simd<1>::constant<0>(), value);
1264
1265        SIMD_type v[4];
1266
1267        v[0] = esimd<fw<2>::value>::mergel(simd<2>::constant<0>(), lo);
1268        v[1] = esimd<fw<2>::value>::mergeh(simd<2>::constant<0>(), lo);
1269        v[2] = esimd<fw<2>::value>::mergel(simd<2>::constant<0>(), hi);
1270        v[3] = esimd<fw<2>::value>::mergeh(simd<2>::constant<0>(), hi);
1271
1272        uint32_t push_count;
1273        for (size_t j = 0, i = 0; i < count; j++, i += 4) {
1274                push_count = (count - i >= 4) ? 4 : count - i;
1275                packed_gids_->push_back(1, (uint32_t *) &(v[j]), push_count);
1276        }
1277}
1278
1279template<>
1280inline void LSSymbolTable::push_gid<2>(const SIMD_type value, const uint32_t count) {
1281        SIMD_type v[2];
1282
1283        v[0] = esimd<fw<2>::value>::mergel(simd<2>::constant<0>(), value);
1284        v[1] = esimd<fw<2>::value>::mergeh(simd<2>::constant<0>(), value);
1285
1286        uint32_t push_count;
1287        for (size_t j = 0, i = 0; i < count; j++, i += 4) {
1288                push_count = (count - i >= 4) ? 4 : count - i;
1289                packed_gids_->push_back(2, (uint32_t *) &(v[j]), push_count);
1290        }
1291}
1292
1293template<>
1294inline void LSSymbolTable::push_gid<3>(const SIMD_type value, const uint32_t count) {
1295        packed_gids_->push_back(3, (uint32_t *) (&value), count);
1296}
1297
1298template<>
1299inline void LSSymbolTable::push_gid<4>(const SIMD_type value, const uint32_t count) {
1300        packed_gids_->push_back(4, (uint32_t *) (&value), count);
1301}
1302
1303template<>
1304inline void LSSymbolTable::push_gid<5>(const SIMD_type value, const uint32_t count) {
1305        SIMD_type t1 = hsimd<64>::packl(simd<1>::constant<0>(), value);
1306        packed_gids_->push_back(5, (uint32_t *) (&t1), count);
1307}
1308
1309template<>
1310inline void LSSymbolTable::push_gid<6>(const SIMD_type value, const uint32_t count) {
1311        SIMD_type t1 = hsimd<64>::packl(simd<1>::constant<0>(), value);
1312        packed_gids_->push_back(6, (uint32_t *) (&t1), count);
1313}
1314
1315template<>
1316inline void LSSymbolTable::push_gid<7>(const SIMD_type value, const uint32_t count) {
1317        SIMD_type t1 = hsimd<64>::packl(simd<1>::constant<0>(), value);
1318        packed_gids_->push_back(7, (uint32_t *) (&t1), count);
1319}
1320
1321template<>
1322inline void LSSymbolTable::push_gid<8>(const SIMD_type value, const uint32_t count) {
1323        SIMD_type t1 = hsimd<64>::packl(simd<1>::constant<0>(), value);
1324        packed_gids_->push_back(8, (uint32_t *) (&t1), count);
1325}
1326
1327#endif
1328
1329#ifdef USE_PACKED_SYMBOLS
1330
1331// Debug
1332void LSSymbolTable::display_gids() {
1333
1334        printf("%30s\n\n", "Length Sorted 32 bit gid values.");
1335
1336        uint32_t lgth;
1337        for (size_t lgth = 1; lgth < this->packed_gids_->rows(); lgth++) {
1338                printf("%29s%zu = ", "L", lgth);
1339                for (size_t i = 0; i < packed_gids_->size(lgth); i++) {
1340                        printf("%d ", packed_gids_->get(lgth, i));
1341                }
1342                printf("\n");
1343        }
1344        printf("\n");
1345}
1346
1347// Debug
1348void LSSymbolTable::display_gid_indices() {
1349        printf("%30s\n\n", "Length Sorted 32 bit document index values.");
1350
1351        uint32_t lgth;
1352        for (size_t lgth = 1; lgth < this->symbol_index_->rows(); lgth++) {
1353                printf("%29s%zu = ", "L", lgth);
1354                for (size_t i = 0; i < this->symbol_index_->size(lgth); i++) {
1355                        printf("%d ", symbol_index_->get(lgth, i));
1356                }
1357                printf("\n");
1358        }
1359        printf("\n");
1360}
1361
1362template<uint32_t L>
1363void LSSymbolTable::display_packed_data() {
1364
1365        uint32_t pack_count = SYMBOL_PACK_COUNT[L];
1366        uint32_t symbol_count;
1367#ifdef USE_SYMBOL_PTRS
1368        symbol_count = this->symbol_value_ptrs_->size(L);
1369#endif
1370
1371#ifdef USE_SYMBOL_VALUES
1372        symbol_count = this->symbol_values_->size(L)/SYMBOL_BYTES[L];
1373#endif
1374
1375        uint32_t non_packed_symbol_count = symbol_count & (pack_count - 1);
1376        uint32_t packed_symbol_count = symbol_count - non_packed_symbol_count; // total 'full' SIMD register bytes
1377
1378        printf("%30s = %d\n", "Symbol Count", symbol_count);
1379        printf("%30s = %d\n", "Symbol Length", L);
1380        printf("%30s = %d\n", "Pack Count", pack_count);
1381        printf("%30s = %d\n", "Packed Symbol Count", packed_symbol_count);
1382        printf("%30s = %d\n", "Non Packed Symbol Count", non_packed_symbol_count);
1383
1384uint32_t i;     
1385#ifdef USE_SYMBOL_PTRS
1386        printf("%30s = %d\n", "Field Width Mapping", fw<L>::value);
1387
1388        // packed symbols
1389        for (i = 0; i < packed_symbol_count; i += pack_count) {
1390                SIMD_type value = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, i)));
1391                print_simd_register("Packed Symbol", value);
1392        }
1393
1394        // non packed symbols
1395        if (non_packed_symbol_count) {
1396                SIMD_type value = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, i)),
1397                                non_packed_symbol_count);
1398                print_simd_register("Non Packed Symbol", value);
1399        }
1400        printf("\n");
1401#endif
1402
1403#ifdef USE_SYMBOL_VALUES
1404        uint32_t total_bytes = this->symbol_values_->size(L);
1405        printf("%30s = %d\n", "Total Bytes", total_bytes);
1406
1407        for(i=0;i<total_bytes;i+=sizeof(SIMD_type)) {
1408                SIMD_type value = sisd_load_aligned((SIMD_type *)&this->symbol_values_->get(L,i));
1409                print_simd_register("Symbol", value);
1410        }
1411        printf("\n");
1412#endif
1413
1414}
1415
1416#endif
1417
Note: See TracBrowser for help on using the repository browser.