Optimize performance of bech32 encoding implementation

[maciejka]

OD Hack

This issue is part of ODHack 4.0:

• description - https://x.com/OnlyDust_com/status/1791035111992934563
• guidelines - https://onlydust.notion.site/ODHack-Common-Guidelines-Project-leads-5e21836f85ad493f9ca429770af0ad40

Task

Here is a bech32 encoding implementation in Cairo:

joyboy/onchain/src/social/bech32.cairo

Line 164 in af4ff42

pub fn encode(hrp: @ByteArray, data: @ByteArray, limit: usize) -> ByteArray {

Your task is to optimize it.

You should provide measurements before and after the optimization.

NOTE: This task is about providing objective code performance optimizations. In case you want to provide a pr, please make sure it contains a description of what and how you want to optimize and measurements before and after optimization. In case you have several optimization ideas please submit them as separate prs.

References

• https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki
• https://github.com/sipa/bech32/blob/master/ref/javascript/bech32.js#L86

Communication

https://t.me/JoyboyStarknet/949

May the Joy be with you!

[kateberryd]

@maciejka I would love to work on this

[juandiegocv27]

Hi, @maciejka I would love to contribute to this task: starting to May 23, 2024, to Completion Date: June 1, 2024, I'm Juan Diego Carballo and I'm a full-stack developer with a software engineer degree, already contributed to other projects and creating an on-chain game. I have experience with Cairo and blockchain development, including implementing and optimizing encoding algorithms. Already follow Joyboy on twitter and joined the Telegram.

[saimeunt]

Hi @maciejka, I recently participated in a gas golfing competition hosted by NodeGuardians and had a lot of fun optimizing contracts in Solidity.

I'm familiar with Cairo and would love to try optimizing the current reference implementation to save some Cairo steps.
I will try to optimize the best I can without sacrificing on the readability of the code, I will study other implementations of Bech32 to search for interesting approaches.

[maciejka]

Hey ODHackers! So many volunteers! Please send me your ideas for optimizations in pm on tg: @aundumla. I will assign the task based on quality of your proposals.

[juandiegocv27]

@maciejka in which channel of the telegram?

[maciejka]

More than one can work on this issue if the ideas for optimizations are different.

[juandiegocv27]

@maciejka sorry, give the issue to someone else

[mathstickz]

i would love to take part in the success of this issue @maciejka

[maciejka]

i would love to take part in the success of this issue @maciejka

Please provide a pr.

[nicosanc]

Out of curiosity (since I am still a beginner), what kind of optimizations are you typically looking for when developing in Cairo? Is it things like bit packing or more complex optimization concepts?

[maciejka]

In this case it would be about minimizing the number of steps and memory usage. czw., 4 lip 2024, 20:33 użytkownik Nicolas Sanchez ***@***.***> napisał:

…

Out of curiosity (since I am still a beginner), what kind of optimizations are you typically looking for when developing in Cairo? Is it things like bit packing or more complex optimization concepts? — Reply to this email directly, view it on GitHub <#74 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AABOTBZRVQXA3PRAPERB3GLZKWIQLAVCNFSM6AAAAABIEFP55WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMBZGQ2DEOBTGI> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[quentin-abei]

Hello, is this still an issue to tackle ? I would want to work on it

[maciejka]

Yes, please provide a pr. pon., 22 lip 2024, 15:26 użytkownik quentin-abei ***@***.***> napisał:

…

Hello, is this still an issue to tackle ? I would want to work on it — Reply to this email directly, view it on GitHub <#74 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AABOTBYB7E32FVGXKVHLNQLZNUCAVAVCNFSM6AAAAABIEFP55WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENBSHE2TSMZQG4> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[quentin-abei]

Are there any available tool to measure cairo code optimization that one could use ?

[maciejka]

Are there any available tool to measure cairo code optimization that one could use ?

Check: https://foundry-rs.github.io/starknet-foundry/snforge-advanced-features/profiling.html

[remybar]

Hi @maciejka !

I made some optimization on the bech32 encode function and if I compare gas consumption, I get an improvement of around 60%.
I did a small scarb project with your reference implementation and the optimized one in this repo: https://github.com/remybar/bech32-optimization.

I will continue in the following days if I find some new ideas ;-)

But I would appreciate any feedback just to be sure it is what you expect.

Note that it uses Cairo 2.7.0.

[maciejka]

It is super cool! Cairo 2.7.0 is the right choice.
It will be easier for me to see the differences and ask questions if you would provide a pr.

[Judacris32]

@maciejka can i be assigned to this issue

[onlydustapp]

Hey @Judacris32!
Thanks for showing interest.
We've created an application for you to contribute to Joyboy Community.
Go check it out on OnlyDust!

[remybar]

It is super cool! Cairo 2.7.0 is the right choice. It will be easier for me to see the differences and ask questions if you would provide a pr.

Hi @maciejka !
Sorry, I just discover your answer, I didn't receive any notification 😅

I'm preparing a PR to bump joyboy to Cairo 2.7.0 but it requires an update from snfoundry. Then I will quickly prepare a PR for this optimization ;-)

[onlydustapp]

Hey @remybar!
Thanks for showing interest.
We've created an application for you to contribute to Joyboy Community.
Go check it out on OnlyDust!

[remybar]

It is super cool! Cairo 2.7.0 is the right choice. It will be easier for me to see the differences and ask questions if you would provide a pr.

I've just created a new PR: #297

Note that this PR is based on my other PR to bump to Cairo 2.7.0 so just look at the bech32.cairo file to see the modifications related to the optimization of bech32.

Don't hesitate if you have any questions ;-) And if you want to see the gain in term of gas, you should have a look at the small project I mentioned before (https://github.com/remybar/bech32-optimization).

[maciejka]

Since this project is paused I am closing this issue in order not to confuse peaople. @remybar thanks for your work.