(Done) April 16th 2025: fast-edn Bug Hunt (Round 2)

[frenchy64]

👍 to RSVP

madclj

Wednesday, April 16th, 2025
6:30 PM to 9:00 PM CT

Location

StartingBlock Madison
821 E Washington Ave 2nd floor · Madison, WI

The building will be locked, here's how to get in

At 6:30pm, please wait by the circled doors (see above) next to the statue between the two buildings. There is usually street parking, alternatively there are parking garages close by.

The doors will be locked. Between 6:30pm-7pm people will periodically check to let you in as a last resort, but please let us know when you expect to arrive ahead of time if you can't make this window.

If you are locked out, please immediately:

• try posting in the GitHub Discussion of the current meetup
• try posting in the #clojure-madison channel of the clojurians slack

Sometimes the guard will let you in if you're lucky, tell them you are here for the Madison Clojure Meetup in the "Digital Den" classroom on floor 2. They can then call the organizers or sometimes take you up themselves.

Topic

Continuing from our previous meetup, we will learn about and hunt for bugs in fast-edn.

Schedule

6:30pm arrive, food & drink provided
7pm, start meetup
9pm end meetup

[frenchy64]

@madclj/meetup April 16th we will host another bug hunt / hacking session on fast-edn. RSVP

[sivakusayan]

Hope I can come even though I didn't make it last week :)

[brunchboy]

Same!

[sivakusayan]

Seems we have two RSVPs - were we still on for today?

[ericnormand]

I won't be able to make it on Wednesday. But I found a link to the project I was thinking of for parsing JSON really quickly: https://github.com/simdjson/simdjson. They use simd instructions to process 64 characters at a time. Here's a talk the creator gave about it: https://www.infoq.com/presentations/simdjson-parser/

[dpetran]

I will also be out this Wednesday, hope it's as much fun as we had last week : )

[frenchy64]

Yes, even if I'm the only one I'm going to use the time to wrap up the code and send it upstream. I'll order less pizza though :) Please update your RSVP by 5:30pm so I can finalize food.

…

-------- Original Message --------

On 4/16/25 08:08, Sayan Sivakumaran wrote: Seems we have two RSVPs - were we still on for today? — Reply to this email directly, [view it on GitHub](#23 (reply in thread)), or [unsubscribe](https://github.com/notifications/unsubscribe-auth/AACGFJC46UL4734VA4CW7TL2ZZI5XAVCNFSM6AAAAAB3ALI7XOVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTEOBVGQ3TKOA). You are receiving this because you authored the thread.Message ID: ***@***.***>

[sivakusayan]

Okay, I'll still come then :)

[brunchboy]

I am coming too.

[frenchy64]

Ordered 3 12" pizzas. I should be there at 6:30pm.

[sivakusayan]

I'll be there at around 7!

[sivakusayan]

I'm downstairs!

[frenchy64]

We reviewed fast-edn since we had a completely distinct set of attendees from last week (apart from me).

This time we concentrated on the benchmarking methodology.

fast-edn uses a benchmarking library called duti that wraps criterium. The benchmarks consist of reading successively larger files of json and edn into memory and running each algorithm over it. The json and edn parsers are tested by using equivalent data in each format.

By reading the string into memory first rather than reading files, we concluded there would probably be less interference from OS-level optimizations around IO, which @sivakusayan was concerned about.

@djwhitt was skeptical that fast-edn's inlining of buffered reading was faster than BufferedReader, so we looked at the general class and quickly realized fast-edn's approach was faster due to no synchronization requirements.

Moving onto the hacking portion of the night:

Our progress for this week, by @frenchy64 @sivakusayan @brunchboy @djwhitt:
madclj/fast-edn@0357298...0354586

Overall PR: madclj/fast-edn#1

We did not write any new tests, in fact rerunning the generative test based on @ericnormand's original idea of removing a single character from otherwise-valid edn yielded 4 more genuine bugs related to sentinel values leaking through to results, which we also fixed.

These are some of our test cases that we fixed---they all now throw instead of returning garbage:

  (require '[fast-edn.core :as edn])

  (edn/read-string "(1])")
  (edn/read-string "[)]")
  (edn/read-string "#{)}")
  (edn/read-string "{)}")
  (edn/read-string "{) )}")
  (edn/read-string "{) 1}")
  (edn/read-string "{) 1 ) 2}")
  (edn/read-string "{) 2 ) 1}")
  (edn/read-string "{1 ) ) 2 ] 3 ] 4}")
  (edn/read-string "{1 )}")
  (edn/read-string "{2 ) 1 )}")

The test also found that symbols starting with digits are allowed by fast-edn. This could be a bug or a documentation improvement, since fast-edn explicitly allows keywords starting with numbers (but we were skeptical that symbols deserve the same special-case since Clojure doesn't allow symbols starting with numbers).

This are test cases for further investigation:

  (edn/read-string "#{A000/0}")
  (edn/read-string "A000/0")

@brunchboy suggested that we add the correct Unmatched delimiter error messages for the cases we fixed. This exercise also helped us better understand the large switch statement in fast-edn, in particular what the possible values passed to this UnexpectedCharacter constructor. We concluded that only closing delimiters are reachable, so no further tests are needed to determine whether we should throw Unmatched delimiter or some other message.

When testing these error messages, we found a suspicious but technically-ok (compared to the rest) case where a divide-by-zero was thrown by fast-edn during (edn/read-string "(1/)"). We left this as future work to improve this error message but were left uneasy about what triggered this error.

@djwhitt suggested we look into https://github.com/kanaka/instacheck for writing more generative tests once we're done with @ericnormand's (I think that one is still failing!).

Open questions:

• @sivakusayan: can we trace the performance improvements of fast-edn throughout its git history?
• @sivakusayan: can we reproduce the benchmarking results?

[frenchy64]

Or at least reach out and explain how you found the issues.

Done!

[ericnormand]

Wow! Thanks for the summary. I wish I could have been there.

I love property-based testing! It finds so many bugs. And it was certainly made easier by having a reference implementation to compare to. Thanks for turning them into upstream PRs and issues.

I wonder about BufferedReader. Maybe it would be worth writing a UnsynchronizedBufferedReader so that the logic wouldn't have to live in the parsing algorithm.

[frenchy64]

And it was certainly made easier by having a reference implementation to compare to.

Yes exactly. Maybe this approach could even be used to test future changes/optimizations to clojure.edn itself by comparing it to previous Clojure versions via a networked repl. You could use the same approach to test parity between tools.reader's clj/s implementations, and the clojure.edn cljs port.

I wonder about BufferedReader. Maybe it would be worth writing a UnsynchronizedBufferedReader so that the logic wouldn't have to live in the parsing algorithm.

One of the open questions was whether having the raw buffer array and mutable position available directly improved performance. Perhaps you can be smarter in some cases?

[ericnormand]

It's possible, but unlikely. I think the big thing is the locking.

For example, the JVM is pretty good about eliminating pointer indirection when it can. It will copy the pointer to the buffer onto the stack (or even into a register) instead of hopping to the object then to the buffer. It needs to be benchmarked, though!

Also, design-wise, it might make sense to keep it all in one class because thread safety is something people often assume about classes. Before I moved it into its own class, I'd probably look for procedural abstractions like the unread() method so it doesn't have so much fiddling with arrays while you're parsing.

[ericnormand]

Also, it feels strange that I was contributing through my test despite not being there. Property-based testing is very generative.