mlt_core/encoder/
optimizer.rs

1use bitvec::vec::BitVec;
2
3use crate::decoder::Morton;
4use crate::encoder::model::{CurveParams, StagedLayer};
5use crate::encoder::{
6    Codecs, Encoder, EncoderConfig, SortStrategy, encode01, spatial_sort_likely_to_help,
7};
8#[cfg(feature = "unstable-v2")]
9use crate::encoder::{WireVersion, encode02};
10use crate::tile::{PropKind, TileLayer};
11use crate::{MltError, MltResult, PropValue};
12
13impl StagedLayer {
14    /// Encode and serialize the layer directly into `enc`, without creating any
15    /// intermediate representation.
16    ///
17    /// This is the hot path inside `TileLayer::encode`: each sort-strategy
18    /// trial calls this method on its own fresh `Encoder`, and only the
19    /// `Encoder` with the smallest `total_len()` is kept.
20    #[hotpath::measure]
21    pub fn encode_into(self, enc: Encoder, codecs: &mut Codecs) -> MltResult<Encoder> {
22        if self.name.is_empty() {
23            return Err(MltError::MissingLayerName);
24        }
25        #[cfg(feature = "unstable-v2")]
26        match enc.config().wire_version() {
27            WireVersion::V01 => encode01::encode_into01(self, enc, codecs),
28            WireVersion::V02 => encode02::encode_into02(self, enc, codecs),
29        }
30        #[cfg(not(feature = "unstable-v2"))]
31        encode01::encode_into01(self, enc, codecs)
32    }
33}
34
35/// Seed the encoder's curve-derived caches so the Hilbert/Morton dictionary
36/// builders skip their min/max scan. `Morton::new` returns `Err` when bits > 16;
37/// `dict_may_be_beneficial` reads `morton_cache.is_none()` and falls back to
38/// a Vec2-only path in that case.
39fn seed_curve_caches(enc: &mut Encoder, curve_params: CurveParams) {
40    enc.hilbert_cache = Some(curve_params);
41    enc.morton_cache = Morton::new(curve_params.bits, curve_params.shift).ok();
42}
43
44/// Feature-count threshold above which the spatial trial is subject to the
45/// bounding-box pruning heuristic.
46const SORT_TRIAL_THRESHOLD: usize = 512;
47
48impl TileLayer {
49    /// Encode a [`TileLayer`] to bytes, automatically optimizing all encoding choices.
50    ///
51    /// This is the primary encoding entry point. It:
52    /// 1. Determines which sort strategies to try based on `cfg`
53    /// 2. Tries each sort strategy, encoding and measuring the output size
54    /// 3. Returns the smallest encoding as a complete layer record (including tag and length prefix)
55    ///
56    /// All encoding choices - sort order, per-stream integer encodings, string compression,
57    /// vertex buffer layout - are selected automatically to minimize output size.
58    #[hotpath::measure]
59    pub fn encode(mut self, cfg: EncoderConfig) -> MltResult<Vec<u8>> {
60        if self.name().is_empty() {
61            return Err(MltError::MissingLayerName);
62        }
63        if self.features().is_empty() {
64            return Ok(Vec::new());
65        }
66        if !cfg.allow_8bit_ints() {
67            self.widen_8bit_ints();
68        }
69
70        let mut sort_by = vec![SortStrategy::Unsorted];
71        let try_spatial_sort =
72            cfg.attempt_spatial_morton_sort() || cfg.attempt_spatial_hilbert_sort();
73        if try_spatial_sort
74            && (self.feature_count() < SORT_TRIAL_THRESHOLD || spatial_sort_likely_to_help(&self))
75        {
76            if cfg.attempt_spatial_morton_sort() {
77                sort_by.push(SortStrategy::SpatialMorton);
78            }
79            if cfg.attempt_spatial_hilbert_sort() {
80                sort_by.push(SortStrategy::SpatialHilbert);
81            }
82        }
83        if cfg.attempt_id_sort() {
84            sort_by.push(SortStrategy::Id);
85        }
86
87        let stats = self.analyze(cfg.allow_shared_dict())?;
88        // Bounds are order-invariant, so this scan is shared across every
89        // sort trial and the encoder's Hilbert/Morton dictionary builders.
90        let curve_params = self.curve_params();
91
92        // `Encoder::preserve_results` clears caches only on the moved-out
93        // archive, so a single seeding here serves every trial that reuses
94        // `enc`.
95        let mut enc = Encoder::new(cfg);
96        seed_curve_caches(&mut enc, curve_params);
97
98        let (last, init) = sort_by.split_last().expect("at least one strategy");
99        if init.is_empty() {
100            let mut codecs = Codecs::default();
101            StagedLayer::from_tile(self, *last, &stats, cfg.tessellate(), curve_params)
102                .encode_into(enc, &mut codecs)?
103        } else {
104            let mut codecs = Codecs::default();
105            enc = {
106                let first = init[0];
107                StagedLayer::from_tile(self.clone(), first, &stats, cfg.tessellate(), curve_params)
108                    .encode_into(enc, &mut codecs)?
109            };
110            let mut best = enc.preserve_results();
111            // Clone for all-but-last strategies
112            for &sort in &init[1..] {
113                let layer = StagedLayer::from_tile(
114                    self.clone(),
115                    sort,
116                    &stats,
117                    cfg.tessellate(),
118                    curve_params,
119                );
120                enc = layer.encode_into(enc, &mut codecs)?;
121                if enc.total_len() < best.total_len() {
122                    best = enc.preserve_results();
123                } else {
124                    // Drop the losing trial's bytes, or the next trial would append to them and overcount its total_len.
125                    enc.clear_results();
126                }
127            }
128            // Last strategy: consume self, no clone
129            let layer = StagedLayer::from_tile(self, *last, &stats, cfg.tessellate(), curve_params);
130            enc = layer.encode_into(enc, &mut codecs)?;
131            if enc.total_len() < best.total_len() {
132                best = enc.preserve_results();
133            }
134            best
135        }
136        .into_layer_bytes()
137    }
138}
139
140/// Row-order-independent presence classification for IDs and properties.
141#[derive(Debug, Clone, Copy, PartialEq, Eq)]
142pub enum Presence {
143    /// No feature has a value for this logical column.
144    AllNull,
145    /// Every feature has a value for this logical column.
146    AllPresent,
147    /// Some, but not all, features have a value for this logical column.
148    Mixed,
149    /// Mixed presence with the same per-feature mask as an earlier property column.
150    ///
151    /// Only tells the stager the column is nullable, same as [`Self::Mixed`]. Which
152    /// columns actually end up sharing one presence bitfield is decided per wire
153    /// format at write time, from the staged masks - see `SharedPresence` in
154    /// `encoder::encode02`.
155    SameAsProp(usize),
156}
157impl Presence {
158    /// Create presence value
159    #[must_use]
160    pub fn from_bits(bits: &BitVec<u8>, existing: &[(BitVec<u8>, usize)]) -> Self {
161        if bits.not_any() {
162            Self::AllNull
163        } else if bits.all() {
164            Self::AllPresent
165        } else if let Some((_, idx)) = existing.iter().find(|(v, _)| v == bits) {
166            Self::SameAsProp(*idx)
167        } else {
168            Self::Mixed
169        }
170    }
171}
172
173/// How a property participates in a shared dictionary group.
174#[derive(Debug, Clone, PartialEq, Eq)]
175pub enum SharedDictRole {
176    /// The property is encoded as a standalone column.
177    None,
178    /// The property is the first column in this group and emits the shared dictionary with this prefix.
179    Owner(String),
180    /// The property is emitted by the group owner at this property index.
181    Member(usize),
182}
183
184/// Row-order-independent facts for a single property column.
185#[derive(Debug, Clone, PartialEq, Eq)]
186pub struct PropertyStats {
187    pub presence: Presence,
188    pub stats: PropertyTypedStats,
189}
190
191/// Row-order-independent layer facts computed once before sort trials.
192#[derive(Debug, Clone, PartialEq, Eq)]
193pub struct LayerStats {
194    pub id: Option<PropertyStats>,
195    pub properties: Vec<PropertyStats>,
196}
197
198/// Row-order-independent value statistics for a property column.
199#[derive(Debug, Clone, Default, PartialEq, Eq)]
200pub enum PropertyTypedStats {
201    /// No present values.
202    #[default]
203    None,
204    Bool,
205    Signed {
206        min: i64,
207        max: i64,
208    },
209    Unsigned {
210        min: u64,
211        max: u64,
212    },
213    F32,
214    F64,
215    String {
216        shared_dict: SharedDictRole,
217    },
218}
219
220impl PropertyTypedStats {
221    #[must_use]
222    pub fn values_fit_u32(&self) -> bool {
223        match self {
224            Self::None | Self::Bool | Self::F32 | Self::F64 | Self::String { .. } => false,
225            Self::Signed { min, max } => *min >= 0 && u32::try_from(*max).is_ok(),
226            Self::Unsigned { max, .. } => u32::try_from(*max).is_ok(),
227        }
228    }
229
230    /// Returns `true` if every value fits in an `i32`.
231    /// Unlike [`Self::values_fit_u32`] this admits negative values.
232    #[must_use]
233    pub fn values_fit_i32(&self) -> bool {
234        match self {
235            Self::None | Self::Bool | Self::F32 | Self::F64 | Self::String { .. } => false,
236            Self::Signed { min, max } => i32::try_from(*min).is_ok() && i32::try_from(*max).is_ok(),
237            Self::Unsigned { max, .. } => i32::try_from(*max).is_ok(),
238        }
239    }
240
241    #[must_use]
242    pub fn shared_dict(&self) -> SharedDictRole {
243        match self {
244            Self::String { shared_dict, .. } => shared_dict.clone(),
245            Self::None
246            | Self::Bool
247            | Self::Signed { .. }
248            | Self::Unsigned { .. }
249            | Self::F32
250            | Self::F64 => SharedDictRole::None,
251        }
252    }
253
254    pub(crate) fn set_shared_dict(&mut self, role: SharedDictRole) {
255        match self {
256            Self::String { shared_dict, .. } => *shared_dict = role,
257            Self::None
258            | Self::Bool
259            | Self::Signed { .. }
260            | Self::Unsigned { .. }
261            | Self::F32
262            | Self::F64 => debug_assert_eq!(role, SharedDictRole::None),
263        }
264    }
265
266    pub(crate) fn push(
267        &mut self,
268        prop: &PropValue,
269        column_idx: usize,
270        property_name: &str,
271    ) -> MltResult<bool> {
272        match prop {
273            PropValue::Bool(Some(_)) => {
274                self.merge_same_kind(Self::Bool, column_idx, property_name)?;
275            }
276            PropValue::I8(Some(v)) => {
277                self.merge_signed(i64::from(*v), column_idx, property_name)?;
278            }
279            PropValue::U8(Some(v)) => {
280                self.merge_unsigned(u64::from(*v), column_idx, property_name)?;
281            }
282            PropValue::I32(Some(v)) => {
283                self.merge_signed(i64::from(*v), column_idx, property_name)?;
284            }
285            PropValue::U32(Some(v)) => {
286                self.merge_unsigned(u64::from(*v), column_idx, property_name)?;
287            }
288            PropValue::I64(Some(v)) => self.merge_signed(*v, column_idx, property_name)?,
289            PropValue::U64(Some(v)) => self.merge_unsigned(*v, column_idx, property_name)?,
290            PropValue::F32(Some(_)) => {
291                self.merge_same_kind(Self::F32, column_idx, property_name)?;
292            }
293            PropValue::F64(Some(_)) => {
294                self.merge_same_kind(Self::F64, column_idx, property_name)?;
295            }
296            PropValue::Str(Some(_)) => self.merge_string(column_idx, property_name)?,
297            PropValue::Bool(None)
298            | PropValue::I8(None)
299            | PropValue::U8(None)
300            | PropValue::I32(None)
301            | PropValue::U32(None)
302            | PropValue::I64(None)
303            | PropValue::U64(None)
304            | PropValue::F32(None)
305            | PropValue::F64(None)
306            | PropValue::Str(None) => return Ok(false),
307        }
308        Ok(true)
309    }
310
311    fn merge_signed(
312        &mut self,
313        value: i64,
314        column_idx: usize,
315        property_name: &str,
316    ) -> MltResult<()> {
317        match self {
318            Self::None => {
319                *self = Self::Signed {
320                    min: value,
321                    max: value,
322                };
323            }
324            Self::Signed { min, max } => {
325                *min = (*min).min(value);
326                *max = (*max).max(value);
327            }
328            Self::Bool | Self::Unsigned { .. } | Self::F32 | Self::F64 | Self::String { .. } => {
329                return mixed_prop_err(column_idx, property_name);
330            }
331        }
332        Ok(())
333    }
334
335    fn merge_unsigned(
336        &mut self,
337        value: u64,
338        column_idx: usize,
339        property_name: &str,
340    ) -> MltResult<()> {
341        match self {
342            Self::None => {
343                *self = Self::Unsigned {
344                    min: value,
345                    max: value,
346                };
347            }
348            Self::Unsigned { min, max } => {
349                *min = (*min).min(value);
350                *max = (*max).max(value);
351            }
352            Self::Bool | Self::Signed { .. } | Self::F32 | Self::F64 | Self::String { .. } => {
353                return mixed_prop_err(column_idx, property_name);
354            }
355        }
356        Ok(())
357    }
358
359    fn merge_string(&mut self, column_idx: usize, property_name: &str) -> MltResult<()> {
360        match self {
361            Self::None => {
362                *self = Self::String {
363                    shared_dict: SharedDictRole::None,
364                };
365            }
366            Self::String { .. } => {}
367            Self::Bool | Self::Signed { .. } | Self::Unsigned { .. } | Self::F32 | Self::F64 => {
368                return mixed_prop_err(column_idx, property_name);
369            }
370        }
371        Ok(())
372    }
373
374    fn merge_same_kind(
375        &mut self,
376        kind: Self,
377        column_idx: usize,
378        property_name: &str,
379    ) -> MltResult<()> {
380        match self {
381            Self::None => *self = kind,
382            Self::Bool if matches!(kind, Self::Bool) => {}
383            Self::F32 if matches!(kind, Self::F32) => {}
384            Self::F64 if matches!(kind, Self::F64) => {}
385            Self::Bool
386            | Self::Signed { .. }
387            | Self::Unsigned { .. }
388            | Self::F32
389            | Self::F64
390            | Self::String { .. } => return mixed_prop_err(column_idx, property_name),
391        }
392        Ok(())
393    }
394}
395
396impl TileLayer {
397    /// Analyze a [`TileLayer`] and return reusable ID/property facts for the optimizer.
398    #[hotpath::measure]
399    pub(crate) fn analyze(&self, allow_shared_dict: bool) -> MltResult<LayerStats> {
400        let mut property_bits = Vec::with_capacity(self.property_names().len());
401        let mut properties = self.analyze_properties(&mut property_bits)?;
402        let id = self.analyze_ids(&property_bits);
403        if allow_shared_dict {
404            self.group_string_properties(&mut properties);
405        }
406        Ok(LayerStats { id, properties })
407    }
408
409    fn analyze_ids(&self, property_bits: &[(BitVec<u8>, usize)]) -> Option<PropertyStats> {
410        let mut min = u64::MAX;
411        let mut max = 0u64;
412        let mut bits = BitVec::<u8>::with_capacity(self.feature_count());
413        for feature in self.features() {
414            if let Some(id) = feature.id() {
415                min = min.min(id);
416                max = max.max(id);
417                bits.push(true);
418            } else {
419                bits.push(false);
420            }
421        }
422        let presence = Presence::from_bits(&bits, property_bits);
423        if presence == Presence::AllNull {
424            None
425        } else {
426            Some(PropertyStats {
427                presence,
428                stats: PropertyTypedStats::Unsigned { min, max },
429            })
430        }
431    }
432
433    fn analyze_properties(
434        &self,
435        property_bits: &mut Vec<(BitVec<u8>, usize)>,
436    ) -> MltResult<Vec<PropertyStats>> {
437        self.property_names()
438            .iter()
439            .enumerate()
440            .map(|(col_idx, name)| -> MltResult<PropertyStats> {
441                let mut kind = None;
442                let mut stats = PropertyTypedStats::default();
443                let mut bits = BitVec::<u8>::with_capacity(self.feature_count());
444                for feature in self.features() {
445                    let prop = feature.properties().get(col_idx);
446                    if let Some(prop_kind) = prop.map(PropKind::from) {
447                        match kind {
448                            Some(kind) if kind != prop_kind => {
449                                return mixed_prop_err(col_idx, name.as_str());
450                            }
451                            None => kind = Some(prop_kind),
452                            _ => {}
453                        }
454                    }
455                    if let Some(prop) = prop
456                        && stats.push(prop, col_idx, name)?
457                    {
458                        bits.push(true);
459                    } else {
460                        bits.push(false);
461                    }
462                }
463
464                let presence = Presence::from_bits(&bits, property_bits);
465                if presence == Presence::Mixed {
466                    property_bits.push((bits, col_idx));
467                }
468                Ok(PropertyStats { presence, stats })
469            })
470            .collect()
471    }
472}
473
474#[inline]
475fn mixed_prop_err<T>(column_idx: usize, property_name: &str) -> MltResult<T> {
476    Err(MltError::MixedPropertyTypes(
477        column_idx,
478        property_name.to_owned(),
479    ))
480}
mlt_core/encoder/optimizer.rs

mlt_core/encoder/
optimizer.rs
