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

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

Minor updates.

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