View Single Post
Old 2020-02-07, 09:47   #15
Mysticial's Avatar
Sep 2016

7×47 Posts

Woah, I go away for a while and didn't notice all these new posts!

Originally Posted by LaurV View Post
Very nice, congrats!

How do you make the base switch "in place"? I have some ideas how to transform from base 2 to base 10 quite fast and also have some checkpoints, but you would need more storage space (it can't really be done "in place"), and I don't believe this is new, for sure somebody else was thinking to it before. I "invented" it long time ago and used it in my programs in the past, but never for such large inputs.
It's not fully in-place in that it doesn't need any auxiliary memory. It needs a lot actually - especially to perform the FFTs.

But there are a few technicalities:

The large multiplications are done in-place. So the output overwrites the inputs. (the multiplication is still done using the FFT scratch buffers)

1) One problem is that I don't support checkpointing inside the large multiplications. Thus I can only checkpoint before or after a large multiplication. But if you encapsulate the multiplication into an indivisible operation, it becomes a destructive operation that destroys the inputs. Thus if something goes wrong inside the multiply, you cannot roll back to before the multiply because you've already destroyed the inputs.

This in-place-ness of the multiplications within the base-conversion will chain up. Thus there's no point where you can do a checkpoint other than before the entire conversion begins.

2) The other problem is that checkpointing is done with file-granularity. I don't support checkpointing parts of a file. The binary->radix conversions involve recursively splitting up the binary input into smaller and smaller portions which you eventually write piecewise into a large output buffer (in the desired radix).

The presents a problem. That output buffer is allocated as single contiguous storage region as a single file. I can't write to parts of the file, checkpoint it, then write to other parts. The reason I can't do that is due sector alignment.

Let's say the following is a partially written sector that's been checkpointed:


Then in a later operation, I want to write out the rest of the sector so that it is:


However. When you access disk, the entire sector must be read/written at once. The later operation needs to do a read-modify-write to data that is part of the previous checkpoint. If something goes wrong during this step, it will corrupt the previous checkpoint!


Long story short, I believe both of issues are surmountable. But I haven't done the necessary research into it yet.

For example, the in-place-ness issue (1) can be overcome by having two working buffers and writing back-and-forth between them. But the base conversion already uses the most storage of the entire computation.

The sector-alignment is probably solvable by keeping a separate mapping that stores backups of all partially written sectors. But saying that this is a mess in the context of the software raid layer and manual error-detection checksums is an understatement.

Last fiddled with by Mysticial on 2020-02-07 at 09:55
Mysticial is offline   Reply With Quote