Recent

Author Topic: Fast Base64 encoding/decoding  (Read 2366 times)

mikerabat

  • New Member
  • *
  • Posts: 39
Fast Base64 encoding/decoding
« on: May 20, 2023, 03:25:34 pm »
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

  • Sr. Member
  • ****
  • Posts: 441
Re: Fast Base64 encoding/decoding
« Reply #1 on: May 23, 2023, 12:03:19 pm »
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?
« Last Edit: May 23, 2023, 12:13:02 pm by Okoba »

mika

  • Full Member
  • ***
  • Posts: 100
Re: Fast Base64 encoding/decoding
« Reply #2 on: May 23, 2023, 05:43:43 pm »
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"
« Last Edit: May 23, 2023, 08:00:51 pm by mika »

dsiders

  • Hero Member
  • *****
  • Posts: 917
Re: Fast Base64 encoding/decoding
« Reply #3 on: May 23, 2023, 06:50:11 pm »
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.
Preview Lazarus 3.99 documentation at: https://dsiders.gitlab.io/lazdocsnext

rvk

  • Hero Member
  • *****
  • Posts: 5490
Re: Fast Base64 encoding/decoding
« Reply #4 on: May 23, 2023, 07:19:40 pm »
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)  :D
« Last Edit: May 23, 2023, 07:21:23 pm by rvk »

dsiders

  • Hero Member
  • *****
  • Posts: 917
Re: Fast Base64 encoding/decoding
« Reply #5 on: May 23, 2023, 07:51:56 pm »

I am assuming FLC was supposed to be FCL... but still impressive speed.
Probably FPC base64 (as base64 has nothing to do with FCL)  :D

Well, it's listed in the FCL reference docs. https://lazarus-ccr.sourceforge.io/docs/fcl/index.html
Preview Lazarus 3.99 documentation at: https://dsiders.gitlab.io/lazdocsnext

rvk

  • Hero Member
  • *****
  • Posts: 5490
Re: Fast Base64 encoding/decoding
« Reply #6 on: May 23, 2023, 08:04:14 pm »
I am assuming FLC was supposed to be FCL... but still impressive speed.
Probably FPC base64 (as base64 has nothing to do with FCL)  :D
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

  • Sr. Member
  • ****
  • Posts: 441
Re: Fast Base64 encoding/decoding
« Reply #7 on: May 24, 2023, 11:08:25 am »
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

  • Administrator
  • Hero Member
  • *
  • Posts: 10937
  • FPC developer.
Re: Fast Base64 encoding/decoding
« Reply #8 on: May 24, 2023, 11:38:11 am »
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

  • Full Member
  • ***
  • Posts: 100
Re: Fast Base64 encoding/decoding
« Reply #9 on: May 24, 2023, 02:47:31 pm »
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.

« Last Edit: May 24, 2023, 02:52:48 pm by mika »

Gustavo 'Gus' Carreno

  • Hero Member
  • *****
  • Posts: 964
  • Professional amateur ;-P
Re: Fast Base64 encoding/decoding
« Reply #10 on: May 24, 2023, 07:11:50 pm »
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 :-[
Lazarus 2.3.0(trunk) FPC 3.3.1(trunk) Ubuntu 23.04 64b Dark Theme
Lazarus 2.2.6(stable) FPC 3.2.2(stable) Ubuntu 23.04 64b Dark Theme
http://github.com/gcarreno

mikerabat

  • New Member
  • *
  • Posts: 39
Re: Fast Base64 encoding/decoding
« Reply #11 on: May 30, 2023, 01:17:08 pm »
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

  • Sr. Member
  • ****
  • Posts: 441
Re: Fast Base64 encoding/decoding
« Reply #12 on: May 30, 2023, 02:37:57 pm »
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

  • New Member
  • *
  • Posts: 18
Re: Fast Base64 encoding/decoding
« Reply #13 on: June 01, 2023, 12:21:58 pm »
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

  • New Member
  • *
  • Posts: 39
Re: Fast Base64 encoding/decoding
« Reply #14 on: June 01, 2023, 03:05:26 pm »
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...)

 

TinyPortal © 2005-2018