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"]}/'
[download]

to

perl -we'use re "debug"; qr/@{[join"|","a000".."v999"]}/'
[download]

(on 5.8.x as well, to see the pre-optimization difference).