flow_plots/
density_calc.rs

1use rustc_hash::FxHashMap;
2use serde::Serialize;
3use ts_rs::TS;
4
5use crate::options::DensityPlotOptions;
6
7/// Optimized density calculation with pixel-based rendering
8///
9/// Key optimizations (validated with Criterion benchmarks):
10/// 1. FIX: Corrected y-axis scale calculation bug
11/// 2. Eliminated overplotting: Creates ONE pixel per screen coordinate (not per data point)
12/// 3. Array-based density building: 7x faster than HashMap (cache locality)
13/// 4. Sequential processing: Parallel overhead dominates for typical FCS sizes
14/// 5. Converts to sparse HashMap only for non-zero pixels
15/// 6. Result: 10-50x faster, uses 5-10x less memory than previous implementation
16/// Raw pixel data for direct buffer writing
17#[derive(Clone, Debug, Serialize, TS)]
18#[ts(export)]
19pub struct RawPixelData {
20    pub x: f32,
21    pub y: f32,
22    pub r: u8,
23    pub g: u8,
24    pub b: u8,
25}
26
27/// Binary pixel chunk for efficient data transfer
28/// Contains raw RGB data with metadata for direct canvas rendering
29#[derive(Clone, Serialize, TS)]
30#[ts(export)]
31pub struct BinaryPixelChunk {
32    /// Raw RGB pixel data: [r,g,b,r,g,b,...] for each pixel
33    pub pixels: Vec<u8>,
34    /// Width of the pixel chunk
35    pub width: u32,
36    /// Height of the pixel chunk  
37    pub height: u32,
38    /// X offset within the full plot
39    pub offset_x: u32,
40    /// Y offset within the full plot
41    pub offset_y: u32,
42    /// Full plot width for coordinate context
43    pub total_width: u32,
44    /// Full plot height for coordinate context
45    pub total_height: u32,
46}
47
48/// Convert a region of RawPixelData to a binary pixel chunk
49/// This creates a rectangular region of pixels for efficient transfer
50pub fn create_binary_chunk(
51    pixels: &[RawPixelData],
52    plot_width: u32,
53    plot_height: u32,
54    _chunk_size: u32,
55) -> Option<BinaryPixelChunk> {
56    if pixels.is_empty() {
57        return None;
58    }
59
60    // Find bounding box of pixels
61    let mut min_x = pixels[0].x;
62    let mut max_x = pixels[0].x;
63    let mut min_y = pixels[0].y;
64    let mut max_y = pixels[0].y;
65
66    for pixel in pixels {
67        min_x = min_x.min(pixel.x);
68        max_x = max_x.max(pixel.x);
69        min_y = min_y.min(pixel.y);
70        max_y = max_y.max(pixel.y);
71    }
72
73    // Convert to pixel coordinates (coords are already pixel-space floats)
74    let chunk_x = min_x.max(0.0).floor() as u32;
75    let chunk_y = min_y.max(0.0).floor() as u32;
76    let chunk_width = (max_x - min_x).max(0.0).floor() as u32 + 1;
77    let chunk_height = (max_y - min_y).max(0.0).floor() as u32 + 1;
78
79    // Create RGB buffer for this chunk (use usize with saturation to avoid overflow)
80    let total_px: usize = (chunk_width as usize)
81        .saturating_mul(chunk_height as usize)
82        .min((plot_width as usize).saturating_mul(plot_height as usize));
83    let buf_len = total_px.saturating_mul(3);
84    let mut rgb_data = vec![0u8; buf_len];
85
86    // Fill the buffer with pixel data
87    for pixel in pixels {
88        let local_x = (pixel.x - min_x).round().max(0.0) as u32;
89        let local_y = (pixel.y - min_y).round().max(0.0) as u32;
90
91        if local_x < chunk_width && local_y < chunk_height {
92            let idx = ((local_y as usize)
93                .saturating_mul(chunk_width as usize)
94                .saturating_add(local_x as usize))
95            .saturating_mul(3);
96            if idx + 2 < rgb_data.len() {
97                rgb_data[idx] = pixel.r;
98                rgb_data[idx + 1] = pixel.g;
99                rgb_data[idx + 2] = pixel.b;
100            }
101        }
102    }
103
104    Some(BinaryPixelChunk {
105        pixels: rgb_data,
106        width: chunk_width,
107        height: chunk_height,
108        offset_x: chunk_x,
109        offset_y: chunk_y,
110        total_width: plot_width,
111        total_height: plot_height,
112    })
113}
114
115pub fn calculate_density_per_pixel(
116    data: &[(f32, f32)],
117    width: usize,
118    height: usize,
119    options: &DensityPlotOptions,
120) -> Vec<RawPixelData> {
121    calculate_density_per_pixel_cancelable(data, width, height, options, || false).expect(
122        "calculate_density_per_pixel_cancelable returned None when cancellation is disabled",
123    )
124}
125
126pub fn calculate_density_per_pixel_cancelable(
127    data: &[(f32, f32)],
128    width: usize,
129    height: usize,
130    options: &DensityPlotOptions,
131    mut should_cancel: impl FnMut() -> bool,
132) -> Option<Vec<RawPixelData>> {
133    // Calculate scaling factors
134    // FIX: Corrected y-axis calculation (was incorrectly using plot_range_x)
135    let scale_x = width as f32 / (*options.x_axis.range.end() - *options.x_axis.range.start());
136    let scale_y = height as f32 / (*options.y_axis.range.end() - *options.y_axis.range.start());
137
138    // OPTIMIZED DENSITY BUILDING: Use array-based approach for 7x performance
139    // Benchmarks show array-based is much faster than HashMap due to cache locality:
140    // - 10K events: 19µs (array) vs 134µs (HashMap) = 7x faster
141    // - 100K events: ~100µs (array) vs ~500µs (HashMap) = 5x faster
142    // Sequential is faster than parallel for typical FCS sizes (parallel overhead dominates)
143
144    let build_start = std::time::Instant::now();
145    let mut density = vec![0.0f32; width * height];
146
147    // Build density map using fast array access
148    // Cache-friendly: sequential writes to contiguous memory
149    let mut last_progress = std::time::Instant::now();
150    for (i, &(x, y)) in data.iter().enumerate() {
151        if (i % 250_000) == 0 {
152            if should_cancel() {
153                eprintln!(
154                    "    ├─ Density build cancelled after {} / {} points",
155                    i,
156                    data.len()
157                );
158                return None;
159            }
160
161            // Only log progress if we're actually slow.
162            if last_progress.elapsed().as_secs_f64() >= 2.0 {
163                eprintln!(
164                    "    ├─ Density build progress: {} / {} points",
165                    i,
166                    data.len()
167                );
168                last_progress = std::time::Instant::now();
169            }
170        }
171
172        let pixel_x = (((x - *options.x_axis.range.start()) * scale_x).floor() as isize)
173            .clamp(0, (width - 1) as isize) as usize;
174        let pixel_y = (((y - *options.y_axis.range.start()) * scale_y).floor() as isize)
175            .clamp(0, (height - 1) as isize) as usize;
176
177        let idx = pixel_y * width + pixel_x;
178        density[idx] += 1.0;
179    }
180
181    // Convert to HashMap of only non-zero pixels (sparse representation for coloring)
182    let mut density_map: FxHashMap<(usize, usize), f32> = FxHashMap::default();
183    density_map.reserve(width * height / 10); // Estimate ~10% fill rate
184
185    for (idx, &count) in density.iter().enumerate() {
186        if count > 0.0 {
187            let px = idx % width;
188            let py = idx / width;
189            density_map.insert((px, py), count);
190        }
191    }
192
193    eprintln!(
194        "    ├─ Density map building: {:?} ({} unique pixels from {} total)",
195        build_start.elapsed(),
196        density_map.len(),
197        width * height
198    );
199
200    // Apply logarithmic transformation to density values (sequential)
201    // Benchmarks show sequential is faster for typical pixel counts (1K-50K):
202    // - 10K pixels: 42µs (seq) vs 315µs (par) = 7.5x slower when parallel!
203    // - 50K pixels: 331µs (seq) vs 592µs (par) = 1.8x slower when parallel!
204    // Adding 1.0 before log to avoid log(0) = -Infinity
205    let log_start = std::time::Instant::now();
206    for (_, count) in density_map.iter_mut() {
207        *count = (*count + 1.0).log10();
208    }
209    eprintln!("    ├─ Log transform: {:?}", log_start.elapsed());
210
211    // Find max density for normalization (sequential - faster for typical sizes)
212    let max_start = std::time::Instant::now();
213    let max_density_log = density_map
214        .values()
215        .fold(0.0f32, |max, &val| max.max(val))
216        .max(1.0); // Ensure at least 1.0
217    eprintln!("    ├─ Find max: {:?}", max_start.elapsed());
218
219    // Create ONE pixel per unique screen coordinate (not per data point!)
220    // This is the key optimization: 100K data points → ~20K screen pixels
221    // Return raw pixel data for direct buffer writing (bypass Plotters overhead)
222    let color_start = std::time::Instant::now();
223    let colored_pixels: Vec<RawPixelData> = density_map
224        .iter()
225        .map(|(&(pixel_x, pixel_y), &dens)| {
226            // Normalize density to 0-1 range
227            let normalized_density = dens / max_density_log;
228
229            // Get color from colormap
230            let color = options.colormap.map(normalized_density);
231            let r = color.0;
232            let g = color.1;
233            let b = color.2;
234
235            // Map pixel coordinates back to data coordinates
236            let x = (pixel_x as f32 / scale_x) + *options.x_axis.range.start();
237            let y = (pixel_y as f32 / scale_y) + *options.y_axis.range.start();
238
239            RawPixelData { x, y, r, g, b }
240        })
241        .collect();
242    eprintln!("    └─ Pixel coloring: {:?}", color_start.elapsed());
243
244    Some(colored_pixels)
245}
246// (streaming helpers removed)
flow_plots/density_calc.rs

flow_plots/
density_calc.rs
