Use `BTreeMap` backing for structs in `sseq`

[JoeyBF]

I feel that replacing the current

pub struct DenseBigradedModule {
    dimensions: OnceBiVec<OnceBiVec<usize>>,
    min_y: i32,
}

with something like

pub struct DenseBigradedModule {
    dimensions: BTreeMap<OrderedBidegree<ByStem>, usize>,
}

would make sense. If we go ahead and refactor the sseq API to use Bidegrees throughout, it would make accessing data easier. I suppose we also reduce allocations and have one less indirection.

Similarly, I suggest we replace

pub struct Sseq<P: SseqProfile = Adams> {
    differentials: BiVec<BiVec<BiVec<Differential>>>,
    permanent_classes: BiVec<BiVec<Subspace>>,
    page_data: BiVec<BiVec<BiVec<Subquotient>>>,
    invalid: BiVec<BiVec<bool>>,
    // ...
}

with

pub struct Sseq<P: SseqProfile = Adams> {
    differentials: BTreeMap<OrderedBidegree<ByStem>, BiVec<Differential>>,
    permanent_classes: BTreeMap<OrderedBidegree<ByStem>, Subspace>,
    page_data: BTreeMap<OrderedBidegree<ByStem>, BiVec<Subquotient>>,
    invalid:  BTreeMap<OrderedBidegree<ByStem>, bool>,
    // ...
}

In fact, now that I write this all out, it might be even more convenient to use some helper struct

pub struct Bigraded<T>(BTreeMap<OrderedBidegree<ByStem>, T>)

everywhere.

[hoodmane]

I think this would be bad for lookup speed. You should actually profile it before doing anything like this.

[JoeyBF]

I think this would be bad for lookup speed. You should actually profile it before doing anything like this.

I agree that I should be careful about that. What kind of benchmark do you think I should add? I suppose the underlying question is what kind of operation on a spectral sequence I should optimize for, which is unclear to me until I implement things further

[hoodmane]

Well my suspicion is that if you did this for our Algebra data structure (for example) and then ran a normal minimal resolution, you'd see a significant slow down.

[hoodmane]

I don't think this should be hard to detect or particularly sensitive to the workload.

[JoeyBF]

I'm not sure what you mean. This crate is not involved in computing minimal resolutions, right now it's mostly just the webserver that uses it to handle its own spectral sequence. Everything happens after having computed Ext.

[hoodmane]

Oh, I'm sorry for misunderstanding. In that case, I think you're right that it probably won't make any observable difference.

[JoeyBF]

Now that got me thinking though. It's often the case that when we use Once(Bi)Vecs we have two or three (or more) nested levels of them. Not just in sseq but also algebra and ext. Maybe it would be nice to abstract that to a map-like data structure that is

• concurrent and lock-free
• insert-only, no deletions or mutations of values, except via inner mutability
• natively k-tuply indexed
• easy and efficient to iterate over any subrange
• as performant as OnceVec for 1-tuple indexes