use std::fs::File;
use std::path::{Path, PathBuf};
use std::time::Instant;
use anyhow::anyhow;
use clap::{value_parser, Arg, Command};
use flate2::read::GzDecoder;
use kiddo_v6::kd_tree::KdTree as KiddoV6KdTree;
use kiddo_v6::leaf_strategies::VecOfArenas;
use kiddo_v6::{DonnellyCyclicSimdFull, DonnellyUnrolled, Eytzinger, ITEM_LEAF_MODE_SORTED};
use memmap::MmapOptions;
use serde::de::DeserializeOwned;
use solvastro::dynamic_index::kdtree_trait::{IndexType, KiddoV6LeafStrategy};
use solvastro::dynamic_index::star_index_container::{
FloatType, KdTreeDescriptor, KiddoV6ItemLeafMode, KiddoV6StemStrategy,
ReadableStarIndexContainer, StarIndexDescriptor, WriteableStarIndexContainer,
};
use solvastro::structs_f64::quad::{Quad, QuadCode};
use solvastro::structs_f64::star::Star;
pub mod csv_record;
pub mod csv_record_hygv3;
pub mod csv_record_mag5cat;
pub mod util;
use util::parse_csv_file;
type StarTreeF32 =
KiddoV6KdTree<f32, u32, Eytzinger, VecOfArenas<f32, u32, 3, 32>, 3, 32, ITEM_LEAF_MODE_SORTED>;
type QuadTreeF32 = KiddoV6KdTree<f32, u32, Eytzinger, VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type StarTreeF64 =
KiddoV6KdTree<f64, u32, Eytzinger, VecOfArenas<f64, u32, 3, 32>, 3, 32, ITEM_LEAF_MODE_SORTED>;
type QuadTreeF64 = KiddoV6KdTree<f64, u32, Eytzinger, VecOfArenas<f64, u32, 4, 32>, 4, 32>;
type DonnellyStarTreeF32 = KiddoV6KdTree<
f32,
u32,
DonnellyUnrolled<4>,
VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type DonnellyQuadTreeF32 =
KiddoV6KdTree<f32, u32, DonnellyUnrolled<4>, VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type DonnellyStarTreeF64 = KiddoV6KdTree<
f64,
u32,
DonnellyUnrolled<3>,
VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type DonnellyMinSummaryStarTreeF64 =
KiddoV6KdTree<f64, u32, DonnellyUnrolled<3>, VecOfArenas<f64, u32, 3, 32>, 3, 32, 8>;
type DonnellyQuadTreeF64 =
KiddoV6KdTree<f64, u32, DonnellyUnrolled<3>, VecOfArenas<f64, u32, 4, 32>, 4, 32>;
type DonnellySimdStarTreeF32 = KiddoV6KdTree<
f32,
u32,
DonnellyCyclicSimdFull<4>,
VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type DonnellySimdQuadTreeF32 =
KiddoV6KdTree<f32, u32, DonnellyCyclicSimdFull<4>, VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type DonnellySimdStarTreeF64 = KiddoV6KdTree<
f64,
u32,
DonnellyCyclicSimdFull<3>,
VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type DonnellySimdMinSummaryStarTreeF64 =
KiddoV6KdTree<f64, u32, DonnellyCyclicSimdFull<3>, VecOfArenas<f64, u32, 3, 32>, 3, 32, 8>;
type DonnellySimdQuadTreeF64 =
KiddoV6KdTree<f64, u32, DonnellyCyclicSimdFull<3>, VecOfArenas<f64, u32, 4, 32>, 4, 32>;
#[derive(Debug, Clone, Copy)]
enum AxisType {
F32,
F64,
}
impl AxisType {
fn parse(value: &str) -> anyhow::Result<Self> {
match value {
"f32" => Ok(Self::F32),
"f64" => Ok(Self::F64),
_ => Err(anyhow!("unsupported axis type: {value}")),
}
}
fn kd_descriptor(
self,
stem_strategy: StemStrategyType,
item_leaf_mode: KiddoV6ItemLeafMode,
) -> KdTreeDescriptor {
KdTreeDescriptor::KiddoV6 {
axis: match self {
Self::F32 => FloatType::Float32,
Self::F64 => FloatType::Float64,
},
index: IndexType::U32,
bucket_size: 32,
leaf_strategy: KiddoV6LeafStrategy::VecOfArenas,
stem_strategy: stem_strategy.kd_descriptor(),
item_leaf_mode,
}
}
}
#[derive(Debug, Clone, Copy)]
enum StemStrategyType {
Eytzinger,
Donnelly,
DonnellySimd,
}
#[derive(Debug, Clone, Copy)]
enum StarItemLeafModeType {
ItemSorted,
EmbeddedMinShift8,
}
impl StarItemLeafModeType {
fn parse(value: &str) -> anyhow::Result<Self> {
match value {
"item-sorted" => Ok(Self::ItemSorted),
"embedded-min-shift-8" => Ok(Self::EmbeddedMinShift8),
_ => Err(anyhow!("unsupported star item-leaf mode: {value}")),
}
}
fn kd_descriptor(self) -> KiddoV6ItemLeafMode {
match self {
Self::ItemSorted => KiddoV6ItemLeafMode::ItemSorted,
Self::EmbeddedMinShift8 => KiddoV6ItemLeafMode::ItemSortedWithEmbeddedMinShift8,
}
}
fn validate(self, axis_type: AxisType, stem_strategy: StemStrategyType) -> anyhow::Result<()> {
match (self, axis_type, stem_strategy) {
(Self::ItemSorted, _, _) => Ok(()),
(
Self::EmbeddedMinShift8,
AxisType::F64,
StemStrategyType::Donnelly | StemStrategyType::DonnellySimd,
) => Ok(()),
(Self::EmbeddedMinShift8, _, _) => Err(anyhow!(
"embedded minimum-item summaries require f64 with donnelly or donnelly-simd"
)),
}
}
}
impl StemStrategyType {
fn parse(value: &str) -> anyhow::Result<Self> {
match value {
"eytzinger" => Ok(Self::Eytzinger),
"donnelly" => Ok(Self::Donnelly),
"donnelly-simd" => Ok(Self::DonnellySimd),
_ => Err(anyhow!("unsupported stem strategy: {value}")),
}
}
fn kd_descriptor(self) -> KiddoV6StemStrategy {
match self {
Self::Eytzinger => KiddoV6StemStrategy::EytzingerPf,
Self::Donnelly => KiddoV6StemStrategy::DonnellyScalar,
Self::DonnellySimd => KiddoV6StemStrategy::DonnellySimd,
}
}
}
#[cfg(not(tarpaulin_include))]
fn main() -> anyhow::Result<()> {
let cli_args = Command::new("rebuild-index")
.arg(
Arg::new("output")
.required(true)
.value_parser(value_parser!(PathBuf)),
)
.arg(
Arg::new("axis-type")
.long("axis-type")
.default_value("f64")
.value_parser(["f32", "f64"]),
)
.arg(
Arg::new("stem-strategy")
.long("stem-strategy")
.default_value("eytzinger")
.value_parser(["eytzinger", "donnelly", "donnelly-simd"]),
)
.arg(
Arg::new("star-item-leaf-mode")
.long("star-item-leaf-mode")
.default_value("item-sorted")
.value_parser(["item-sorted", "embedded-min-shift-8"]),
)
.get_matches();
let output = cli_args
.get_one::<PathBuf>("output")
.expect("output is required");
let axis_type = AxisType::parse(
cli_args
.get_one::<String>("axis-type")
.expect("axis type has a default"),
)?;
let stem_strategy = StemStrategyType::parse(
cli_args
.get_one::<String>("stem-strategy")
.expect("stem strategy has a default"),
)?;
let star_item_leaf_mode = StarItemLeafModeType::parse(
cli_args
.get_one::<String>("star-item-leaf-mode")
.expect("star item-leaf mode has a default"),
)?;
star_item_leaf_mode.validate(axis_type, stem_strategy)?;
let quads: Vec<Quad> =
read_from_file("hyg-cg-v2-quad-list.bincode.gz").expect("could not load quads");
let codes: Vec<QuadCode> =
read_from_file("hyg-cg-v2-code-list.bincode.gz").expect("could not load codes");
let csv_file = File::open("hygdata_v3.csv")?;
let stars = parse_csv_file(csv_file);
let descriptor = StarIndexDescriptor::new(
FloatType::Float64,
axis_type.kd_descriptor(stem_strategy, star_item_leaf_mode.kd_descriptor()),
axis_type.kd_descriptor(stem_strategy, KiddoV6ItemLeafMode::Unsorted),
);
let dyn_index = match axis_type {
AxisType::F32 => build_f32_index(descriptor, stem_strategy, stars, quads, &codes)?,
AxisType::F64 => build_f64_index(
descriptor,
stem_strategy,
star_item_leaf_mode,
stars,
quads,
&codes,
)?,
};
println!("{:#?}", dyn_index);
let output_str = output
.to_str()
.ok_or_else(|| anyhow!("output path is not valid UTF-8"))?;
dyn_index.save(output_str)?;
let start = Instant::now();
let file = File::open(output)?;
let buf = unsafe { MmapOptions::new().map(&file)? };
let reloaded_index = ReadableStarIndexContainer::load(&buf)?;
println!("{:#?}", reloaded_index);
println!("Load time: {:?}", start.elapsed());
Ok(())
}
fn read_from_file<T: DeserializeOwned>(filename: &str) -> anyhow::Result<T> {
let file = File::open(Path::new(filename))?;
let decompressor = GzDecoder::new(file);
Ok(bincode::deserialize_from(decompressor)?)
}
fn build_f32_index(
descriptor: StarIndexDescriptor,
stem_strategy: StemStrategyType,
stars: Vec<Star>,
quads: Vec<Quad>,
codes: &[QuadCode],
) -> anyhow::Result<WriteableStarIndexContainer> {
let (kd_stars, kd_codes): (
Box<dyn solvastro::dynamic_index::kdtree_trait::KdTree<3>>,
Box<dyn solvastro::dynamic_index::kdtree_trait::KdTree<4>>,
) = match stem_strategy {
StemStrategyType::Eytzinger => (
Box::new(build_star_tree_f32(&stars)?),
Box::new(build_quad_tree_f32(codes)?),
),
StemStrategyType::Donnelly => (
Box::new(build_donnelly_star_tree_f32(&stars)?),
Box::new(build_donnelly_quad_tree_f32(codes)?),
),
StemStrategyType::DonnellySimd => (
Box::new(build_donnelly_simd_star_tree_f32(&stars)?),
Box::new(build_donnelly_simd_quad_tree_f32(codes)?),
),
};
Ok(WriteableStarIndexContainer {
descriptor,
vec_stars: stars,
vec_quads: quads,
kd_stars,
kd_codes,
})
}
fn build_f64_index(
descriptor: StarIndexDescriptor,
stem_strategy: StemStrategyType,
star_item_leaf_mode: StarItemLeafModeType,
stars: Vec<Star>,
quads: Vec<Quad>,
codes: &[QuadCode],
) -> anyhow::Result<WriteableStarIndexContainer> {
let (kd_stars, kd_codes): (
Box<dyn solvastro::dynamic_index::kdtree_trait::KdTree<3>>,
Box<dyn solvastro::dynamic_index::kdtree_trait::KdTree<4>>,
) = match (stem_strategy, star_item_leaf_mode) {
(StemStrategyType::Eytzinger, StarItemLeafModeType::ItemSorted) => (
Box::new(build_star_tree_f64(&stars)?),
Box::new(build_quad_tree_f64(codes)?),
),
(StemStrategyType::Donnelly, StarItemLeafModeType::ItemSorted) => (
Box::new(build_donnelly_star_tree_f64(&stars)?),
Box::new(build_donnelly_quad_tree_f64(codes)?),
),
(StemStrategyType::DonnellySimd, StarItemLeafModeType::ItemSorted) => (
Box::new(build_donnelly_simd_star_tree_f64(&stars)?),
Box::new(build_donnelly_simd_quad_tree_f64(codes)?),
),
(StemStrategyType::Donnelly, StarItemLeafModeType::EmbeddedMinShift8) => (
Box::new(build_donnelly_min_summary_star_tree_f64(&stars)?),
Box::new(build_donnelly_quad_tree_f64(codes)?),
),
(StemStrategyType::DonnellySimd, StarItemLeafModeType::EmbeddedMinShift8) => (
Box::new(build_donnelly_simd_min_summary_star_tree_f64(&stars)?),
Box::new(build_donnelly_simd_quad_tree_f64(codes)?),
),
(StemStrategyType::Eytzinger, StarItemLeafModeType::EmbeddedMinShift8) => {
unreachable!("unsupported item-leaf mode was validated before construction")
}
};
Ok(WriteableStarIndexContainer {
descriptor,
vec_stars: stars,
vec_quads: quads,
kd_stars,
kd_codes,
})
}
fn build_star_tree_f32(stars: &[Star]) -> anyhow::Result<StarTreeF32> {
let points = stars
.iter()
.map(|star| star.spherical_array().map(|axis| axis as f32))
.collect::<Vec<_>>();
let tree: StarTreeF32 = KiddoV6KdTree::builder()
.with_item_sorted_leaves()
.build_from_slice(&points)?;
Ok(tree)
}
fn build_star_tree_f64(stars: &[Star]) -> anyhow::Result<StarTreeF64> {
let points = stars.iter().map(Star::spherical_array).collect::<Vec<_>>();
let tree: StarTreeF64 = KiddoV6KdTree::builder()
.with_item_sorted_leaves()
.build_from_slice(&points)?;
Ok(tree)
}
fn build_donnelly_star_tree_f32(stars: &[Star]) -> anyhow::Result<DonnellyStarTreeF32> {
let points = stars
.iter()
.map(|star| star.spherical_array().map(|axis| axis as f32))
.collect::<Vec<_>>();
let tree: DonnellyStarTreeF32 = KiddoV6KdTree::builder()
.with_item_sorted_leaves()
.build_from_slice(&points)?;
Ok(tree)
}
fn build_donnelly_star_tree_f64(stars: &[Star]) -> anyhow::Result<DonnellyStarTreeF64> {
let points = stars.iter().map(Star::spherical_array).collect::<Vec<_>>();
let tree: DonnellyStarTreeF64 = KiddoV6KdTree::builder()
.with_item_sorted_leaves()
.build_from_slice(&points)?;
Ok(tree)
}
fn build_donnelly_min_summary_star_tree_f64(
stars: &[Star],
) -> anyhow::Result<DonnellyMinSummaryStarTreeF64> {
let points = stars.iter().map(Star::spherical_array).collect::<Vec<_>>();
let tree: DonnellyMinSummaryStarTreeF64 = KiddoV6KdTree::builder()
.with_embedded_min_item_shifted_summary::<8>()
.build_from_slice(&points)?;
Ok(tree)
}
fn build_donnelly_simd_star_tree_f32(stars: &[Star]) -> anyhow::Result<DonnellySimdStarTreeF32> {
let points = stars
.iter()
.map(|star| star.spherical_array().map(|axis| axis as f32))
.collect::<Vec<_>>();
let tree: DonnellySimdStarTreeF32 = KiddoV6KdTree::builder()
.with_item_sorted_leaves()
.build_from_slice(&points)?;
Ok(tree)
}
fn build_donnelly_simd_star_tree_f64(stars: &[Star]) -> anyhow::Result<DonnellySimdStarTreeF64> {
let points = stars.iter().map(Star::spherical_array).collect::<Vec<_>>();
let tree: DonnellySimdStarTreeF64 = KiddoV6KdTree::builder()
.with_item_sorted_leaves()
.build_from_slice(&points)?;
Ok(tree)
}
fn build_donnelly_simd_min_summary_star_tree_f64(
stars: &[Star],
) -> anyhow::Result<DonnellySimdMinSummaryStarTreeF64> {
let points = stars.iter().map(Star::spherical_array).collect::<Vec<_>>();
let tree: DonnellySimdMinSummaryStarTreeF64 = KiddoV6KdTree::builder()
.with_embedded_min_item_shifted_summary::<8>()
.build_from_slice(&points)?;
Ok(tree)
}
fn codes_f32(codes: &[QuadCode]) -> Vec<[f32; 4]> {
codes
.iter()
.map(|code| code.map(|axis| axis as f32))
.collect()
}
fn build_quad_tree_f32(codes: &[QuadCode]) -> anyhow::Result<QuadTreeF32> {
Ok(QuadTreeF32::new_from_slice(&codes_f32(codes))?)
}
fn build_quad_tree_f64(codes: &[QuadCode]) -> anyhow::Result<QuadTreeF64> {
Ok(QuadTreeF64::new_from_slice(codes)?)
}
fn build_donnelly_quad_tree_f32(codes: &[QuadCode]) -> anyhow::Result<DonnellyQuadTreeF32> {
Ok(DonnellyQuadTreeF32::new_from_slice(&codes_f32(codes))?)
}
fn build_donnelly_quad_tree_f64(codes: &[QuadCode]) -> anyhow::Result<DonnellyQuadTreeF64> {
Ok(DonnellyQuadTreeF64::new_from_slice(codes)?)
}
fn build_donnelly_simd_quad_tree_f32(
codes: &[QuadCode],
) -> anyhow::Result<DonnellySimdQuadTreeF32> {
Ok(DonnellySimdQuadTreeF32::new_from_slice(&codes_f32(codes))?)
}
fn build_donnelly_simd_quad_tree_f64(
codes: &[QuadCode],
) -> anyhow::Result<DonnellySimdQuadTreeF64> {
Ok(DonnellySimdQuadTreeF64::new_from_slice(codes)?)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn builds_trees_for_every_supported_k6_configuration() {
let stars = vec![
Star::new(0.0, 0.0, 1.0, None, "0".to_owned()),
Star::new(1.0, 1.0, 2.0, None, "1".to_owned()),
];
let codes = [[0.1, 0.2, 0.3, 0.4], [0.2, 0.3, 0.4, 0.5]];
assert!(build_star_tree_f32(&stars).unwrap().item_sorted_leaves());
assert!(build_star_tree_f64(&stars).unwrap().item_sorted_leaves());
assert!(build_donnelly_star_tree_f32(&stars)
.unwrap()
.item_sorted_leaves());
assert!(build_donnelly_star_tree_f64(&stars)
.unwrap()
.item_sorted_leaves());
assert!(build_donnelly_simd_star_tree_f32(&stars)
.unwrap()
.item_sorted_leaves());
assert!(build_donnelly_simd_star_tree_f64(&stars)
.unwrap()
.item_sorted_leaves());
assert_eq!(
build_donnelly_min_summary_star_tree_f64(&stars)
.unwrap()
.item_leaf_mode(),
kiddo_v6::ItemLeafMode::SortedWithEncodedMin { shift: 8 }
);
assert_eq!(
build_donnelly_simd_min_summary_star_tree_f64(&stars)
.unwrap()
.item_leaf_mode(),
kiddo_v6::ItemLeafMode::SortedWithEncodedMin { shift: 8 }
);
assert_eq!(build_quad_tree_f32(&codes).unwrap().size(), codes.len());
assert_eq!(build_quad_tree_f64(&codes).unwrap().size(), codes.len());
assert_eq!(
build_donnelly_quad_tree_f32(&codes).unwrap().size(),
codes.len()
);
assert_eq!(
build_donnelly_quad_tree_f64(&codes).unwrap().size(),
codes.len()
);
assert_eq!(
build_donnelly_simd_quad_tree_f32(&codes).unwrap().size(),
codes.len()
);
assert_eq!(
build_donnelly_simd_quad_tree_f64(&codes).unwrap().size(),
codes.len()
);
}
#[test]
fn embedded_min_summaries_require_f64_donnelly() {
assert!(StarItemLeafModeType::EmbeddedMinShift8
.validate(AxisType::F64, StemStrategyType::DonnellySimd)
.is_ok());
assert!(StarItemLeafModeType::EmbeddedMinShift8
.validate(AxisType::F32, StemStrategyType::DonnellySimd)
.is_err());
assert!(StarItemLeafModeType::EmbeddedMinShift8
.validate(AxisType::F64, StemStrategyType::Eytzinger)
.is_err());
}
}