I ran in to this too and talked with
demerphq about it. It looks to me like
when an alternation series gets too long, it uses BRANCHJ instead of BRANCH, because LONGJMP is needed to jump to the end of the series. And I think the trie optimization only kicks in for BRANCHes. This may be simple to fix or it may
not. Any hardy souls out there want to dive in?
A simple testcase: compare
perl -we'use re "debug"; qr/@{[join"|","a000".."u999"]}/'
to
perl -we'use re "debug"; qr/@{[join"|","a000".."v999"]}/'
(on 5.8.x as well, to see the pre-optimization difference).