Debian Codegraph @

.cargo/vendor/transpose/src/out_of_place.rs

raw
1 // Block size used by the tiling algoritms
2 const BLOCK_SIZE: usize = 16;
3 // Number of segments used by the segmented block transpose function
4 const NBR_SEGMENTS: usize = 4;
5 // recursively split data until the number of rows and columns is below this number
6 const RECURSIVE_LIMIT: usize = 128;
7
8 // Largest size for for using the direct approach
9 const SMALL_LEN: usize = 255;
10 // Largest size for using the tiled approach
11 const MEDIUM_LEN: usize = 1024*1024;
12
13
14 /// Given an array of size width * height, representing a flattened 2D array,
15 /// transpose the rows and columns of that 2D array into the output.
16 /// Benchmarking shows that loop tiling isn't effective for small arrays.
17 unsafe fn transpose_small<T: Copy>(input: &[T], output: &mut [T], width: usize, height: usize) {
18 for x in 0..width {
19 for y in 0..height {
20 let input_index = x + y * width;
21 let output_index = y + x * height;
22
23 *output.get_unchecked_mut(output_index) = *input.get_unchecked(input_index);
24 }
25 }
26 }
27
28 // Transpose a subset of the array, from the input into the output. The idea is that by transposing one block at a time, we can be more cache-friendly
29 // SAFETY: Width * height must equal input.len() and output.len(), start_x + block_width must be <= width, start_y + block height must be <= height
30 unsafe fn transpose_block<T: Copy>(input: &[T], output: &mut [T], width: usize, height: usize, start_x: usize, start_y: usize, block_width: usize, block_height: usize) {
31 for inner_x in 0..block_width {
32 for inner_y in 0..block_height {
33 let x = start_x + inner_x;
34 let y = start_y + inner_y;
35
36 let input_index = x + y * width;
37 let output_index = y + x * height;
38
39 *output.get_unchecked_mut(output_index) = *input.get_unchecked(input_index);
40 }
41 }
42 }
43
44 // Transpose a subset of the array, from the input into the output. The idea is that by transposing one block at a time, we can be more cache-friendly
45 // SAFETY: Width * height must equal input.len() and output.len(), start_x + block_width must be <= width, start_y + block height must be <= height
46 // This function works as `transpose_block`, but also divides the loop into a number of segments. This makes it more cache fiendly for large sizes.
47 unsafe fn transpose_block_segmented<T: Copy>(input: &[T], output: &mut [T], width: usize, height: usize, start_x: usize, start_y: usize, block_width: usize, block_height: usize) {
48 let height_per_div = block_height/NBR_SEGMENTS;
49 for subblock in 0..NBR_SEGMENTS {
50 for inner_x in 0..block_width {
51 for inner_y in 0..height_per_div {
52 let x = start_x + inner_x;
53 let y = start_y + inner_y + subblock*height_per_div;
54
55 let input_index = x + y * width;
56 let output_index = y + x * height;
57
58 *output.get_unchecked_mut(output_index) = *input.get_unchecked(input_index);
59 }
60 }
61 }
62 }
63
64 /// Given an array of size width * height, representing a flattened 2D array,
65 /// transpose the rows and columns of that 2D array into the output.
66 /// This algorithm divides the input into tiles of size BLOCK_SIZE*BLOCK_SIZE,
67 /// in order to reduce cache misses. This works well for medium sizes, when the
68 /// data for each tile fits in the caches.
69 fn transpose_tiled<T: Copy>(input: &[T], output: &mut [T], input_width: usize, input_height: usize) {
70
71 let x_block_count = input_width / BLOCK_SIZE;
72 let y_block_count = input_height / BLOCK_SIZE;
73
74 let remainder_x = input_width - x_block_count * BLOCK_SIZE;
75 let remainder_y = input_height - y_block_count * BLOCK_SIZE;
76
77 for y_block in 0..y_block_count {
78 for x_block in 0..x_block_count {
79 unsafe {
80 transpose_block(
81 input, output,
82 input_width, input_height,
83 x_block * BLOCK_SIZE, y_block * BLOCK_SIZE,
84 BLOCK_SIZE, BLOCK_SIZE,
85 );
86 }
87 }
88
89 //if the input_width is not cleanly divisible by block_size, there are still a few columns that haven't been transposed
90 if remainder_x > 0 {
91 unsafe {
92 transpose_block(
93 input, output,
94 input_width, input_height,
95 input_width - remainder_x, y_block * BLOCK_SIZE,
96 remainder_x, BLOCK_SIZE);
97 }
98 }
99 }
100
101 //if the input_height is not cleanly divisible by BLOCK_SIZE, there are still a few rows that haven't been transposed
102 if remainder_y > 0 {
103 for x_block in 0..x_block_count {
104 unsafe {
105 transpose_block(
106 input, output,
107 input_width, input_height,
108 x_block * BLOCK_SIZE, input_height - remainder_y,
109 BLOCK_SIZE, remainder_y,
110 );
111 }
112 }
113
114 //if the input_width is not cleanly divisible by block_size, there are still a few rows+columns that haven't been transposed
115 if remainder_x > 0 {
116 unsafe {
117 transpose_block(
118 input, output,
119 input_width, input_height,
120 input_width - remainder_x, input_height - remainder_y,
121 remainder_x, remainder_y);
122 }
123 }
124 }
125 }
126
127 /// Given an array of size width * height, representing a flattened 2D array,
128 /// transpose the rows and columns of that 2D array into the output.
129 /// This is a recursive algorithm that divides the array into smaller pieces, until they are small enough to
130 /// transpose directly without worrying about cache misses.
131 /// Once they are small enough, they are transposed using a tiling algorithm.
132 fn transpose_recursive<T: Copy>(input: &[T], output: &mut [T], row_start: usize, row_end: usize, col_start: usize, col_end: usize, total_columns: usize, total_rows: usize) {
133 let nbr_rows = row_end - row_start;
134 let nbr_cols = col_end - col_start;
135 if (nbr_rows <= RECURSIVE_LIMIT && nbr_cols <= RECURSIVE_LIMIT) || nbr_rows<=2 || nbr_cols<=2 {
136 let x_block_count = nbr_cols / BLOCK_SIZE;
137 let y_block_count = nbr_rows / BLOCK_SIZE;
138
139 let remainder_x = nbr_cols - x_block_count * BLOCK_SIZE;
140 let remainder_y = nbr_rows - y_block_count * BLOCK_SIZE;
141
142
143 for y_block in 0..y_block_count {
144 for x_block in 0..x_block_count {
145 unsafe {
146 transpose_block_segmented(
147 input, output,
148 total_columns, total_rows,
149 col_start + x_block * BLOCK_SIZE, row_start + y_block * BLOCK_SIZE,
150 BLOCK_SIZE, BLOCK_SIZE,
151 );
152 }
153 }
154
155 //if the input_width is not cleanly divisible by block_size, there are still a few columns that haven't been transposed
156 if remainder_x > 0 {
157 unsafe {
158 transpose_block(
159 input, output,
160 total_columns, total_rows,
161 col_start + x_block_count * BLOCK_SIZE, row_start + y_block * BLOCK_SIZE,
162 remainder_x, BLOCK_SIZE);
163 }
164 }
165 }
166
167 //if the input_height is not cleanly divisible by BLOCK_SIZE, there are still a few rows that haven't been transposed
168 if remainder_y > 0 {
169 for x_block in 0..x_block_count {
170 unsafe {
171 transpose_block(
172 input, output,
173 total_columns, total_rows,
174 col_start + x_block * BLOCK_SIZE, row_start + y_block_count * BLOCK_SIZE,
175 BLOCK_SIZE, remainder_y,
176 );
177 }
178 }
179
180 //if the input_width is not cleanly divisible by block_size, there are still a few rows+columns that haven't been transposed
181 if remainder_x > 0 {
182 unsafe {
183 transpose_block(
184 input, output,
185 total_columns, total_rows,
186 col_start + x_block_count * BLOCK_SIZE, row_start + y_block_count * BLOCK_SIZE,
187 remainder_x, remainder_y);
188 }
189 }
190 }
191 } else if nbr_rows >= nbr_cols {
192 transpose_recursive(input, output, row_start, row_start + (nbr_rows / 2), col_start, col_end, total_columns, total_rows);
193 transpose_recursive(input, output, row_start + (nbr_rows / 2), row_end, col_start, col_end, total_columns, total_rows);
194 } else {
195 transpose_recursive(input, output, row_start, row_end, col_start, col_start + (nbr_cols / 2), total_columns, total_rows);
196 transpose_recursive(input, output, row_start, row_end, col_start + (nbr_cols / 2), col_end, total_columns, total_rows);
197 }
198 }
199
200
201 /// Transpose the input array into the output array.
202 ///
203 /// Given an input array of size input_width * input_height, representing flattened 2D data stored in row-major order,
204 /// transpose the rows and columns of that input array into the output array
205 /// ```
206 /// // row-major order: the rows of our 2D array are contiguous,
207 /// // and the columns are strided
208 /// let input_array = vec![ 1, 2, 3,
209 /// 4, 5, 6];
210 ///
211 /// // Treat our 6-element array as a 2D 3x2 array, and transpose it to a 2x3 array
212 /// let mut output_array = vec![0; 6];
213 /// transpose::transpose(&input_array, &mut output_array, 3, 2);
214 ///
215 /// // The rows have become the columns, and the columns have become the rows
216 /// let expected_array = vec![ 1, 4,
217 /// 2, 5,
218 /// 3, 6];
219 /// assert_eq!(output_array, expected_array);
220 ///
221 /// // If we transpose it again, we should get our original data back.
222 /// let mut final_array = vec![0; 6];
223 /// transpose::transpose(&output_array, &mut final_array, 2, 3);
224 /// assert_eq!(final_array, input_array);
225 /// ```
226 ///
227 /// # Panics
228 ///
229 /// Panics if `input.len() != input_width * input_height` or if `output.len() != input_width * input_height`
230 pub fn transpose<T: Copy>(input: &[T], output: &mut [T], input_width: usize, input_height: usize) {
231 assert_eq!(input_width.checked_mul(input_height), Some(input.len()));
232 assert_eq!(input.len(), output.len());
233 if input.len() <= SMALL_LEN {
234 unsafe { transpose_small(input, output, input_width, input_height) };
235 }
236 else if input.len() <= MEDIUM_LEN {
237 transpose_tiled(input, output, input_width, input_height);
238 }
239 else {
240 transpose_recursive(input, output, 0, input_height, 0, input_width, input_width, input_height);
241 }
242 }
243