search

keep-starknet-strange / joyboy

Decentralized social built with Nostr and powered by Starknet account abstraction.
https://joyboy.community
MIT License
68 stars 50 forks source link

Optimize performance of `bech32` encoding implementation #74

Closed maciejka closed 3 days ago

maciejka commented 3 months ago

OD Hack

This issue is part of ODHack 4.0:

Task

Here is a bech32 encoding implementation in Cairo: https://github.com/keep-starknet-strange/joyboy/blob/af4ff42f0036739a196a498da5b03933fc3ae16f/onchain/src/social/bech32.cairo#L164 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

Communication

https://t.me/JoyboyStarknet/949

May the Joy be with you!

kateberryd commented 3 months ago

@maciejka I would love to work on this

juandiegocv27 commented 3 months ago

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 commented 3 months ago

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 commented 3 months ago

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 commented 3 months ago

@maciejka in which channel of the telegram?

maciejka commented 3 months ago

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

juandiegocv27 commented 3 months ago

@maciejka sorry, give the issue to someone else

mathstickz commented 2 months ago

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

maciejka commented 2 months ago

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

Please provide a pr.

nicosanc commented 2 months ago

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 commented 2 months ago

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 https://github.com/keep-starknet-strange/joyboy/issues/74#issuecomment-2209442832, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABOTBZRVQXA3PRAPERB3GLZKWIQLAVCNFSM6AAAAABIEFP55WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMBZGQ2DEOBTGI . You are receiving this because you were mentioned.Message ID: @.***>

quentin-abei commented 1 month ago

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

maciejka commented 1 month ago

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 https://github.com/keep-starknet-strange/joyboy/issues/74#issuecomment-2242959307, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABOTBYB7E32FVGXKVHLNQLZNUCAVAVCNFSM6AAAAABIEFP55WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENBSHE2TSMZQG4 . You are receiving this because you were mentioned.Message ID: @.***>

quentin-abei commented 1 month ago

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

maciejka commented 1 month ago

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 commented 1 month ago

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 commented 1 month ago

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 commented 3 weeks ago

@maciejka can i be assigned to this issue

onlydustapp[bot] commented 3 weeks ago

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 commented 3 weeks ago

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[bot] commented 3 weeks ago

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 commented 3 weeks ago

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: https://github.com/keep-starknet-strange/joyboy/pull/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 commented 3 days ago

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