source: perf/stream2runs/src/stream2runs.h @ 1179

Last change on this file since 1179 was 1179, checked in by ksherdy, 8 years ago

Refactor stream2runs. Extract interface methods. Remove DEFAULT compile time flag.

File size: 6.1 KB
Line 
1/*
2 *  stream2runs.h
3 *
4 *  Created on: 21-Sep-2009
5 *  Author: ksherdy
6 *  Description: Length Sorted Symbol Table (Key Sorted)
7 *
8 *  #define BRANCH_REDUCTION - generates branch reducing implementation
9 */
10
11#ifndef STREAM2RUNS_H
12#define STREAM2RUNS_H
13
14#include "stdlib.h"
15
16// Templated SIMD               // size_t
17#define TEMPLATED_SIMD_LIB
18#include "../lib/lib_simd.h"    // cflz
19
20static inline size_t scan_thru(size_t cursor, size_t stream);
21static inline size_t scan_thru(size_t cursor, size_t stream) {
22        return (cursor + stream) & (~stream);
23}
24
25void print_chars(const char * str, size_t length);
26void print_chars(const char * str, size_t length) {
27
28        for(int i=0;i<length;i++) {
29                printf("%c",str[i]);
30        }
31        printf("\n");
32       
33}
34
35/**
36 * Given a span stream buffer (bit stream) returns parallel arrays of span starts, span lengths, and the span count.
37 *
38 * bit_stream_buffer                                    IN  - Bit stream input buffer.
39 * bit_stream_general_register_blocks                   IN  - Stream buffer count expressed as a count of the number of general registers widths ().
40 * start_index                                          OUT - Bit stream span start positions, 0-based index.
41 * lengths                                              OUT - Bit stream span lengths.
42 * span_count                                           OUT - Total span count. start_index & lengths are parallel arrays.
43 *
44 * This routine leverages carry propagation together with the compiler builtin instruction to efficiently scan/calculate the start position
45 * and length of bit stream spans.
46 *
47 * --- Performance Analysis ---
48 *
49 * For each general register width we load a general register with the next bitstream value and complement this value.
50 *
51 * For each scan_thru operation some probability exists that we hit a general register width boundary and the
52 * condition cursor != 0 *may be* mispredicted. 
53 *
54 * One hypothesis is that for short spans and gaps branch mis-predictions are reduced since the branch predictor may
55 * be a better to train on this conditional.
56 *
57 * A second hypothesis is that the most significant penalty of short spans and gaps is that short spans and gaps result
58 * in more calls to the count forward leading zeroes.
59 *
60 */
61
62#ifdef BRANCH_REDUCTION
63
64static inline void stream2runs(unsigned char * bit_stream_buffer, size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count);
65static inline void stream2runs(unsigned char * bit_stream_buffer, size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count) {
66       
67  size_t stream = 0;
68  size_t not_stream = 0;
69  size_t index = 0;
70
71 
72  size_t buffer_index = 0;
73  size_t block_index = 0;
74  size_t cursor = 1;
75 
76  size_t leading_zeroes = 0;
77  size_t stream_shift = 0;
78 
79  if(0 < bit_stream_general_register_blocks) {
80          stream = *(((size_t *) bit_stream_buffer) + index);
81          not_stream = ~stream;
82  }
83   
84  while(buffer_index < bit_stream_general_register_blocks) {
85 
86          while(1) { 
87                         
88                        cursor = scan_thru(cursor, not_stream);
89                       
90                        if(cursor != 0) {
91                                leading_zeroes = cfzl(cursor);
92                                start_index[index] = leading_zeroes + (buffer_index << 3);
93
94                                stream_shift = leading_zeroes >> 3;
95                                buffer_index += stream_shift;
96                                stream = *((size_t *) (bit_stream_buffer + buffer_index));
97                                not_stream = ~(*((size_t *) (bit_stream_buffer + buffer_index)));
98                                cursor = cursor >> (stream_shift << 3);                 
99                                break;
100                               
101                        } else {
102                                buffer_index++;
103                                if(buffer_index >= bit_stream_general_register_blocks) {
104                                        break;
105                                }                               
106                                stream = *((size_t *) (bit_stream_buffer + buffer_index));
107                                not_stream = ~stream;
108                                cursor = 1;
109                        }
110               
111          }
112         
113          while(1) {
114                 
115                        cursor = scan_thru(cursor, stream);
116                       
117                        if(cursor != 0) {
118                                leading_zeroes = cfzl(cursor);
119                                lengths[index] = leading_zeroes + (buffer_index << 3) - start_index[index];
120                                index++;
121       
122                                stream_shift = leading_zeroes >> 3;
123                                buffer_index += stream_shift;
124                                stream = *((size_t *) (bit_stream_buffer + buffer_index ));
125                                not_stream = ~(*((size_t *) (bit_stream_buffer + buffer_index )));
126                                cursor = cursor >> (stream_shift << 3);
127                                break;
128                               
129                        } else {
130                                buffer_index++;
131                                if(buffer_index >= bit_stream_general_register_blocks) {
132                                        break;
133                                }                               
134                                stream = *((size_t *) (bit_stream_buffer + buffer_index));
135                                not_stream = ~stream;
136                                cursor = 1;
137                        }                 
138          }
139  }
140 
141  *span_count = index;
142}
143
144#else // Default Implementation
145
146#define SIMD_REGISTER_BIT_WIDTH (sizeof(SIMD_type) << 3)
147#define REGISTER_BIT_WIDTH (sizeof(void *) << 3)
148
149static inline void stream2runs(size_t bit_stream_buffer [], size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count);
150static inline void stream2runs(size_t bit_stream_buffer [], size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count) {
151       
152  size_t stream = 0;
153  size_t not_stream = 0;
154  size_t parallel_arrays_index = 0;
155 
156  size_t block_index = 0;
157  size_t cursor = 1;
158 
159  size_t leading_zeroes = 0;
160  size_t shift = 0;
161 
162  if(0 < bit_stream_general_register_blocks) {
163          stream = bit_stream_buffer[parallel_arrays_index];
164          not_stream = ~stream;
165  }
166   
167  while(block_index < bit_stream_general_register_blocks) {
168 
169          while(1) { 
170                         
171                        cursor = scan_thru(cursor, not_stream);
172                       
173                        if(cursor != 0) { // found span start
174                                leading_zeroes = cfzl(cursor);
175                                start_index[parallel_arrays_index] = leading_zeroes + (block_index * REGISTER_BIT_WIDTH); // stores (memory writes) may be the largest cost                             
176                                break;
177                        } else {
178                                block_index++;
179                                if(block_index >= bit_stream_general_register_blocks) { // this *should* be predicted correctly
180                                        break; 
181                                }
182                                stream = bit_stream_buffer[block_index];
183                                not_stream = ~stream;
184                                cursor = 1;
185                        }       
186          }
187         
188          while(1) {
189                 
190                        cursor = scan_thru(cursor, stream);
191                       
192                        if(cursor != 0) {       
193                                lengths[parallel_arrays_index] = cfzl(cursor) + (block_index * REGISTER_BIT_WIDTH) - start_index[parallel_arrays_index];
194                                parallel_arrays_index++;
195                                break;
196                        } else {
197                                block_index++;
198                                if(block_index >= bit_stream_general_register_blocks) { 
199                                        break; 
200                                }
201                                stream = bit_stream_buffer[block_index];
202                                not_stream = ~stream;
203                                cursor = 1;
204                        }                 
205          }
206  }
207 
208  *span_count = parallel_arrays_index;
209}
210
211#endif
212
213
214#endif // STREAM2RUNS_H
Note: See TracBrowser for help on using the repository browser.