| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
Codecov Report❌ Patch coverage is 90.22222% with 22 lines in your changes missing coverage. Please review.
... and 8 files with indirect coverage changes 🚀 New features to boost your workflow:
|
Sorry, something went wrong.
There was a problem hiding this comment.
Thanks for starting to have a look at this!
I am trying to go over this in slightly more detail, but let me put some global remarks/thoughts I have here:
The first thing relates to the NTuple case for large N. I absolutely agree that the compile time of that is untenable, and should be addressed, and while I would probably do something similar to you, there is something that looks a bit off to first constructing a vector, only to then immediately convert it to a tuple. I would definitely prefer to keep the small N values non-allocating and fully specialized, if at all possible, since otherwise this is a lot of extra code to maintain and we might also consider just keeping everything SectorDict and optimizing that.
In some sense, if we are already allocating a vector, we might as well just store the result as a vector and see if the extra pointer indirections actually matter, which I'm not expecting them to do.
So basically, I think it might be useful to just have a GradedSpace{I, Vector{Int}} implementation that has the exact same semantics as the tuple version, but avoids the compile-time issues.
@assume_effects :foldable function sectorstoragetype(::Type{I}) where {I <: Sector}
if Base.IteratorSize(values(I)) isa Union{HasLength, HasShape}
N = length(values(I))
return N <= 10 ? NTuple{N, Int} : Vector{Int}
else
return SectorDict{I, Int}
end
end
Base.getindex(::SpaceTable, I::Type{<:Sector}) = GradedSpace{I, sectorstoragetype(I)}A different thing that could be relevant is that in principle we could also reduce the compile time issues for the smaller N values by "blocking" the compiled types, e.g. NTuple{N, Int} for the next value in the set N = 1,2,4,8,16,32 which basically trades some compilation for storage efficiency (see e.g. the packages SmallCollections.jl or similar. I do however think that this probably hints at the Vector{Int} approach being more appropriate anyways.
A final comment is that I think one of the inefficiencies of the implementations e.g. for truncated factorizations is probably that we are always constructing these as SectorDicts, which is a bit wasteful in the case of NTuple storage. There might be additional optimizations in that realm as well.
Sorry, something went wrong.
…into bd/gradedspace-storage
|
Short summary of the recent commits:
Some comments of the review I didn't immediately address, and why:
There was a suggestion to run some DMRG code with these changes which I haven't done yet. I believe since that will be dominated by LAPACK, the only thing I'd have to look for is no notable regression. So if things remain in the same ballpark (or just compile at all, since that was an issue), then I think things are fine. |
Sorry, something went wrong.
|
My apologies for the slow review. I find the current code quite difficult to properly review, as I am not entirely convinced of the structure. I do like the modifications to GradedSpace with a cutoff based on length, which could be even smaller for all I am concerned (e.g. 4 or 8 instead of 32). Also the use of mergewith as a paradigm, and its specialized implementation for SortedVectorDict, is very clever. However, I am less convinced by the FullVectorDict implementation in auxiliary.jl and the associated sectormap paradigm. As far as I can tell, this seems to be used only to support the truncation. One issue is that I view auxiliary.jl as a place for some very basic auxiliary tools that do not depend on the rest of the package, but are used at various places throughout the package. I.e., it would be code that could be moved to its own package if there were a more general use for it. This seems somewhat orthogonal to the FullVectorDict and sectormap paradigm, which are only used in truncation.jl and which depend strongly on methods from the Sector interface, (even though FullVectorDict looks like a generic AbstractDict subtype, aside from the restriction on the key type parameter K). I still have to read through truncation.jl to see if there is anything better I could come up with, which is what I will do next. The reason for bringing this up and being difficult is that I want to ensure that the code remains logically structured and therefore easier to maintain. |
Sorry, something went wrong.
|
In particular, is all the code of FullVectorDict worth the performance gain instead of just using SectorDict = SortedVectorDict for all sectors when applying sectormap, irrespective of whether the GradedSpace uses NTuple or not? |
Sorry, something went wrong.
`FullVectorDict`/`sectormap` existed only to give the truncation code a dense
"sector => index" map for tuple-backed spaces. Their call sites all go through
`pairs(::SectorVector)`, which materialises a `SectorDict` anyway, so the dense
map bought little for a lot of `Sector`-specific machinery in `auxiliary/`.
Every truncation index map is a plain `SectorDict` again; instead
`pairs(::SectorVector)` is built directly from the already-sorted structure
rather than by repeated sorted insertion. The storage-specialised
`truncate_space` methods are kept, since they never used the dense map.
Also from the review:
- `⊖` for dict storage reuses `_sortedmerge`, whose `_keepunmatched` trait is
generalised into per-side `_unmatched1`/`_unmatched2` hooks
- `_ntuple_storage_threshold` -> `_NTUPLE_STORAGE_THRESHOLD`, lowered to 8
- `ZNSpace{N}` deprecated in favour of `Vect[ZNIrrep{N}]`, which the alias can
no longer track once `N` exceeds the threshold
- drop the over-strong `I == Trivial` assert in `truncate_space`, and name the
index variables `ind`/`inds` instead of shadowing the sector type `I`
Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
`valtype(::SectorVector)` claims a `SubArray`, but `view` of a GPU array is itself a `CuArray`/`ROCArray`, so pinning the element type to `valtype` broke every GPU factorization. Take the element type from the views instead. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
- add `TupleGradedSpace{I,N}` / `DictGradedSpace{I}` aliases for the two
variants `sectorstoragetype` selects between, and use them for dispatch
- `SubtractDims` doubles as the unmatched handler for `⊖`, and is used for the
tuple variant as well, so both paths share one callable
- `_sortedmerge` takes the unmatched handlers as arguments; `mergewith` selects
them inline
- `pairs(::SectorVector)` is lazy, like `blocks(::AbstractTensorMap)`: every
consumer only iterates, and lookups go through the vector itself
- document `sectorstoragetype`, whose docstring interpolates the threshold
Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
|
I think this is ready for another round of review. I've incorporated the code style suggestions and variable names, removed the FullVectorDict and slightly improved the pairs(::SectorVector) iterator to compensate for that. It would probably be good to remeasure performance and re-evaluate after merging this PR, but since there are already quite a few useful changes here I'd vote in favor of merging this first. Small thing I noted, the type alias ZNSpace{N} is no longer compatible with the split sectorstoragetype based on the sectortype alone, as this will give a wrong result as soon as N > tuple_threshold. I think it's fine to simply deprecate this, the only other thing I can come up with is to change this to ZNSpace(N)(args...), which also looks a bit off to me. |
Sorry, something went wrong.
| newdims = MutableNTuple(ntuple(_ -> 0, StaticLength(N))) | ||
| for (c, ind) in pairs(inds) | ||
| d = dim(V, c) | ||
| n_write = findindex(vals, c) | ||
| @inbounds newdims[n_write] = _blocklength(d, ind) | ||
| end |
There was a problem hiding this comment.
Do we need this construction via MutableNTuple? How about
| newdims = MutableNTuple(ntuple(_ -> 0, StaticLength(N))) | |
| for (c, ind) in pairs(inds) | |
| d = dim(V, c) | |
| n_write = findindex(vals, c) | |
| @inbounds newdims[n_write] = _blocklength(d, ind) | |
| end | |
| newdims = ntuple(N) do n | |
| c = vals[n] | |
| d = V.dims[n] | |
| ind = inds[c] | |
| return _blocklength(d, ind) | |
| end |
or thus as onliner
| newdims = MutableNTuple(ntuple(_ -> 0, StaticLength(N))) | |
| for (c, ind) in pairs(inds) | |
| d = dim(V, c) | |
| n_write = findindex(vals, c) | |
| @inbounds newdims[n_write] = _blocklength(d, ind) | |
| end | |
| newdims = ntuple(n->_blocklength(V.dims[n], inds[vals[n]]), N) |
So we are then not iterating the inds dictionary, but since we anyway know that N is pretty small in this case, I do wonder how severe the key lookups are.
(We are also not needing to do findindex(vals, c) anymore, which might sometimes be a simple calculation, but sometimes also an inefficient lookup).
Sorry, something went wrong.
There was a problem hiding this comment.
Good call, although it requires a little more care because not all inds[vals[n]] will work, but I think I can actually work around this because we always have either V.dims[n] == 0 or the key is present
Sorry, something went wrong.
There was a problem hiding this comment.
I left some smaller final comments, but otherwise approved.
Sorry, something went wrong.
|
I have not actually approved since I hadn't checked wether automerge was on, and wanted to give you time to look at my suggestions. However, feel free to merge after having looked at them. |
Sorry, something went wrong.
Co-authored-by: Jutho <Jutho@users.noreply.github.com>
…inds Address Jutho's final review round on #511: - replace `StaticLength(N)` with plain `N` (constant propagation makes the old TupleTools artefact unnecessary now that N is already a type parameter), and drop the now-dead `TupleTools: StaticLength` imports. - rewrite `truncate_space(::TupleGradedSpace, inds)` as a pure `ntuple` closure instead of mutating a `MutableNTuple`, guarding zero-dimension sectors before indexing into `inds` (which only holds keys for sectors with nonzero dimension). - `truncate_space(::DictGradedSpace, inds)` no longer collects and sorts: `inds` (whether a `SectorDict` or a `SectorVector`, depending on the truncation strategy) already iterates in sorted order by sector. - drop the now-unused `MutableNTuple`/`findindex` imports in the factorizations submodule. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com>
`pairs(::SectorVector)` is intentionally lazy (a `Base.Generator`), so comparing it directly to a `Dict` with `==` silently evaluates to `false` rather than erroring, since no `==` is defined between those unrelated iterator types. Collect it before comparing. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com>
| Back | FazBrowse Home | New Git URL |
This is somewhat connected to what I was doing in QuantumKitHub/TensorKitSectors.jl#106, but beneficial for all sector types. Since I've firsthand experienced how my code transitioned from being unusable to performing well by going from NTuple storage to SectorDict storage, I thought it was about time to look at these storage paths.
I had two options going into this. The one I'm still looking into is seeing whether there's a cutoff (or range) where NTuple storage severely starts underperforming. The other approach I'm taking in this PR is to specialise GradedSpace functions and constructors based on their storage type. The overarching problems I tried to fix were the following:
Summary of changes I made:
Benchmarks
I tested Julia 1.10.10 (LTS) and 1.12.6 (stable) since I think those are the two versions most people are on. For the NTuple storage sector types, I tested N = 2 / 8 / 64 / 256 / 1296 with Z2Irrep / ZNIrrep{8} / Z4Irrep⊠^3 / Z4Irrep⊠^4 / ZNIrrep{6}⊠^6. I also tested N = 15625 with ZNIrrep{5}⊠^6 where possible, which is important to mention. For the SectorDict I tested U1Irrep with charges -6:6, -50:50, and -200:200 (13/101/401 sectors).
And here the many many numbers. I spared my sanity by having a robot friend write this in markdown.
Constructor compile time (the Val effect)
DetailsN=15625 before does not complete (at least within 5 minutes on my laptop) on either version. After: 973 ms (1.10.10), 1.00 s (1.12.6).
NTuple storage (after above compilation time)
DetailsAnd now just the N=15625 case separately, also just after only as before doesn't finish:
On the ⊖/1.12.6 number: the first call at this N takes ~290-353s on 1.12.6 specifically (reproduced 3×), but the second call in the same session takes ~1.2s, matching 1.10.10's steady-state ~1.1s for the same op at the same N. Only compiling the whole ⊖ method together on 1.12.6 is this slow. I didn't look deeper into this, also since its use-case is extremely limited for this large N.
SectorDict U1Irrep
Details(Negative) conclusions/remarks from the benchmarks:
All in all, these are improvements, notably the SectorDict. So it makes you wonder if there's in fact some cutoff N above which you want to say SizeUnknown to the SectorValues' length 🤔