Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize quadratic to linear time complexity, various crucial fixes, fix benchmarks #46

Open
wants to merge 4 commits into
base: master
Choose a base branch
from

Conversation

appgurueu
Copy link

@appgurueu appgurueu commented Dec 17, 2022

Changes:

  • Fix write time complexity being quadratic: Write to a rope rather than recursively concatenating strings; fixes Encoding runs in worst-case quadratic time #45
  • Fix number encoding: For 64-bit floats, up to 17 digits must be written; presumably fixes Large numbers serialized incorrectly #41
  • Fix benchmarks: Do GC before benchmarking to not drag down implementations that run later, inheriting the garbage of previous implementations. Also, bump up the runs by 10x because otherwise the variance is simply too large.
  • Fix tests: Using full double precision unfortunately means unclean numbers pop up.
  • Optimize string parsing: Use a rope for string parsing to bring it back down to linear time complexity (also leads to less garbage); fixes There is an idea to optimize the code for json.lua #34

Choices involved:

  • A rope is passed to all write functions. Alternatively, a "write" function could be passed; that would incur function call overhead however, in exchange for making the code slightly more readable.
  • rope[#rope + 1] is preferred over table.insert due to better performance on PUC Lua.
  • The rope parameter could be gotten rid of by using closures for all write functions instead and making the rope / write function an upvalue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
1 participant