Puregrain.Internal.Fifo
- Package
- purescript-puregrain
- Repository
- roman-mkh/puregrain
The queues that carry error fractions from the pixel that produces them to the pixel that receives them, and their implementations. Internal: may change without notice.
#Fifo Source
class Fifo :: (Type -> Type) -> Constraintclass Fifo (f :: Type -> Type) where
A FIFO-like container of Numbers, used to hold error-diffusion
fractions for a single kernel offset as they travel from the pixel
that produced them to the pixel that consumes them.
Every method below is called exactly once per pixel (or once per
row, where noted) in the dithering hot path, so the real-world
performance of the whole algorithm is dominated by how cheaply an
instance can implement these four operations. Each instance should
document its own actual complexity per method, and should aim for
the target given here wherever its underlying representation
allows it — falling short of the target is not a correctness bug,
but it will show up directly in docs/benchmarks-fifo.md.
Members
replicate :: forall a. Int -> a -> f aenqueue :: forall a. f a -> a -> f aenqueue fifo xappendsxto the tail offifo, returning the extendedFifo.fifoitself is left unchanged — anyone still holding a reference to it must keep seeing the original, unextended contents (this is a pure, persistent operation, not a mutation).Called exactly once per pixel, for every offset with
dy == 0(current) and every offset withdy > 0(building). This is the single hottest operation in the whole algorithm: itsO(n)cost onData.List.Lazy— wherengrows up to the image width over the course of a row — is exactly what produced theO(width²)-per-row,O(width³)-per-square-image blowup recorded indocs/benchmarks-fifo.md.Target complexity: O(1) amortized. An instance that can only offer O(n) here reintroduces precisely the bug this class exists to fix.
dequeue :: forall a. f a -> Maybe { head :: a, tail :: f a }dequeue fiforemoves and returns the value at the head offifo, together with the remainingFifo— orNothingiffifois empty.Called exactly once per pixel, for every offset being read this row (
currentandmatured). Together withenqueue, this bounds the per-pixel cost of the whole algorithm.Nothingis a real, expected outcome only when padding runs out at the very edge of the image.Puregrain.Internal.Steptreats any otherNothingas a violated invariant and crashes loudly rather than silently substituting a value — instances must not paper over emptiness themselves (e.g. by returning a fabricated zero).Target complexity: O(1) amortized.
replace :: forall a. Ring a => Int -> f a -> f areplace skip fifodrops the firstskipelements from the front offifoand appendsskipzeros to the tail, returning aFifoof the SAME LENGTH as the input.skipis always small (bounded by the kernel's horizontal reach — seePuregrain.Internal.Kernel.skipFor), butfifoitself may be as long as the image width by the time this is called.Called once per row, per offset with a negative
dx, inPuregrain.Internal.Row.commitBuilding— this re-aligns a fully-built row's worth of error fractions with the next row's pixel positions before it's handed off to itsDelayLineslot.This is its own method — rather than being left for callers to express as "drop, then append a small replicated tail" — because that composition is O(n) on a plain singly-linked list even though
skipis small (the append has to walk and rebuild the entire dropped-and-kept prefix). An instance backed by a structure with cheap concatenation (e.g. a finger tree, where append is O(log(min(n1, n2)))) should implementreplaceusing that capability directly, to actually realize the better complexity — not by delegating todrop+<>.Target complexity: better than O(n) where the underlying structure allows it. O(n) is acceptable only if the instance genuinely cannot do better, and should be called out as a known limitation in that instance's own documentation.
Instances
Fifo ListSanity-check baseline instance: this is the representation the project used before
class Fifoexisted.enqueueandreplaceare both O(n) here (a plain singly-linked list has no cheap way to append at the tail) — an instance ofFifousing this should reproduce theO(N³)scaling recorded for square images indocs/benchmarks-fifo.md, not improve on it. Kept around specifically to verify that the abstraction itself introduces no regression relative to the pre-class Fifocode, and as a point of comparison for theCatQueueinstance below.Fifo ListFifo ArrayFifo CatQueueThe production default (
Puregrain.Internal.Image.ditherImage). It replacedData.Sequence.Seq, the finger tree that first fixed the O(N³) scaling (docs/benchmarks-fifo.md), on 2026-10-03: about 3.6× faster, and a registry package instead of a git fork (docs/benchmarks-dithering.md).Data.CatQueue(packagecatenable-lists) is Okasaki's strict two-list queue: a front list to dequeue from and a back list, newest first, to enqueue onto.enqueue(snoc) is O(1).dequeue(uncons) is O(1) amortized: when the front list runs out, it reverses the back list once, in O(n).replace skipisskipdequeues followed byskipenqueues ofzero, so O(skip) amortized, andskipis at most the kernel's reach.replicatebuilds straight into the front list, so a fresh queue never needs reversing.The amortized bounds hold only if each queue version is used once: an old version used again would redo the same reversal.
stepandstepRowuse them that way, since every operation's result replaces its input. Reusing a whole row's state (the publicDithering) is fine: stepping from it again redoes that row's work, the reversal included, and no more.
- Modules
- Puregrain
- Puregrain.
Cells - Puregrain.
Dither - Puregrain.
Gamma - Puregrain.
Internal. Exact - Puregrain.
Internal. Fifo - Puregrain.
Internal. Gamma - Puregrain.
Internal. Image - Puregrain.
Internal. Kernel - Puregrain.
Internal. Quantize - Puregrain.
Internal. Row - Puregrain.
Internal. SelfCheck - Puregrain.
Internal. State - Puregrain.
Internal. Step - Puregrain.
Internal. Util - Puregrain.
Kernel - Puregrain.
Machine. C64 - Puregrain.
Machine. ZxSpectrum - Puregrain.
Ordered - Puregrain.
Palette - Puregrain.
Palette. Presets - Puregrain.
Pixel - Puregrain.
Quantize - Puregrain.
SelfCheck
replicate n xbuilds aFifocontaining exactlyncopies ofx, in order — sodequeueon the result yieldsxexactlyntimes before theFifobecomes empty.Called once per row, to build the leading zero-padding for an offset with a positive
dx(seePuregrain.Internal.Kernel.paddingFor), and to build the leading zero-padding for thecurrent/buildinglayers at the start of every row.nis always small — bounded by the kernel's horizontal reach (its largestdx), never by image width or height.Target complexity: O(n). Since
nis always small, this is never the bottleneck regardless of the instance's constant factors.