Fast Base64 encoding/decoding

[mikerabat]

For all who are interesed in a fast Base64 encoding and decoding using AVX instruction:
https://github.com/mikerabat/FastBase64

have fun
and let me know if somethings not working

[Okoba]

Faster code is always welcomed!
I tested your project. It is not Lazarus or FPC friendly, it needs clean-up to make it work.
And I am curious, what is the speed in GB?

[mika]

And I am curious, what is the speed in GB?

Impressive 2,7 GB/s. 

FCL base64 - encoding 25 times and decoding 50 times slower.

Edit: fixed typo in "FCL"

[dsiders]

And I am curious, what is the speed in GB?

Impressive 2,7 GB/s. 

FLC base64 - encoding 25 times and decoding 50 times slower.

I am assuming FLC was supposed to be FCL... but still impressive speed.

[rvk]

And I am curious, what is the speed in GB?

Impressive 2,7 GB/s. 
FLC base64 - encoding 25 times and decoding 50 times slower.

I am assuming FLC was supposed to be FCL... but still impressive speed.

Probably FPC base64 (as base64 has nothing to do with FCL) 

[dsiders]

I am assuming FLC was supposed to be FCL... but still impressive speed.

Probably FPC base64 (as base64 has nothing to do with FCL) 

Well, it's listed in the FCL reference docs. https://lazarus-ccr.sourceforge.io/docs/fcl/index.html

[rvk]

I am assuming FLC was supposed to be FCL... but still impressive speed.

Probably FPC base64 (as base64 has nothing to do with FCL) 

Well, it's listed in the FCL reference docs. https://lazarus-ccr.sourceforge.io/docs/fcl/index.html

Woops, you are correct  I was confusing this with LCL.

[Okoba]

And I am curious, what is the speed in GB?

Impressive 2,7 GB/s. 

FCL base64 - encoding 25 times and decoding 50 times slower.

Edit: fixed typo in "FCL"

I guess mORMot speed is higher, near 7 GB/s.
And the source document says Base64 with speed of memory copy, so I guess there is something wrong in the port or tests.

[marcov]

Can also be a different machine with a different memory speed :-)

Anyway, unrolling 4 times to a 96 byte block saves some redundant loads, so there is room for improvement.

But for who is encoding/decoding mail attachments so critical?

[mika]

I guess mORMot speed is higher, near 7 GB/s.

You are right.
New test results including mORMot

FastBase64
encoding      2.703 GB/s
decoding      2.915 GB/s

mORMot2 (AVX2 version)
encoding      4.386 GB/s
decoding      5.587 GB/s

mORMot2 (pascal version)
encoding      1.274 GB/s
decoding      1.383 GB/s

FCL base64
encoding      0.123 GB/s
decoding      0.059 GB/s

Those speeds are measured with large ~1GB random data. With small inputs speeds would be different.

Anyway, unrolling 4 times to a 96 byte block saves some redundant loads, so there is room for improvement.

But for who is encoding/decoding mail attachments so critical?

Compared to mORMot2 pascal implementation of base64, we have a lot to improve. Maybe "copy&paste" from mORMot2 would work?
Very simple improvement would be to replace Move(...,3) in FCL base64 encode with single simple assign and that would double the speed.

[Gustavo 'Gus' Carreno]

Hey mikerabat,

This is a wonderful achievement !!!

Cheers,
Gus
P.S.: While the compliment is oh-so very deserved, this is also a lame trick to have feed back on this thread

[mikerabat]

Can also be a different machine with a different memory speed :-)

Anyway, unrolling 4 times to a 96 byte block saves some redundant loads, so there is room for improvement.

But for who is encoding/decoding mail attachments so critical?

I guess so - the mOrmot code is impressive and really fast - they really got the algorithm rockin. Basically they use the same
operands but I think they did a more clever way of loading/storing the data.... I think the paper I referenced was
a predecessor but Synapse enhanced that even further....

I will check the loop unrolling - at least for the encoding part

[Okoba]

ab, the author of mORMot is a master of assembly. I always enjoy his work despite looking scary from outside. I suggest checking mORMot2 for anyone checked mORMot and scared by the size and complication.

[Stefan Glienke]

I guess so - the mOrmot code is impressive and really fast - they really got the algorithm rockin. Basically they use the same
operands but I think they did a more clever way of loading/storing the data.... I think the paper I referenced was
a predecessor but Synapse enhanced that even further....

I will check the loop unrolling - at least for the encoding part

mormot is doing 48byte->64byte per loop iteration, you are doing 24byte->32byte

[mikerabat]

I will check the loop unrolling - at least for the encoding part
[/quote]
mormot is doing 48byte->64byte per loop iteration, you are doing 24byte->32byte
[/quote]

Yes this is correct - though... I did some small tests trying to emulate 48Bytes and still did
not achieve the throughput as they did.
What I think is really weired - since they basically use the same algorithm. What I noticed is
that they use a wired load/store scheme. Instead of loading a register in one op they
load first the lower parts of both registers then the upper parts basically doubling the amount of
load/store operations - it seems that does the trick but nevertheless ... it's weird...
and also I tried to just duplicate the block that does the encoding magic whereas they do
an interleaved double block - this maybe get better throughput too.... but.. I'm still a bit testing (though I'm quite
happy about the throughput anyway...)