<< Back to previous view

[MATCH-1] Investigate non-overlapping pattern optimization via pre-allocated exception for backtracking Created: 04/Sep/11  Updated: 28/Jul/13  Resolved: 28/Sep/11

Status: Closed
Project: core.match
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: David Nolen Assignee: David Nolen
Resolution: Completed Votes: 0
Labels: None


 Description   

The red black tree balance pattern mentioned by tgk generates enough code that the JVM will not inline it. Maranget's algorithm basically implements backtracking by passing along wildcard matches with actual matches. For non-overlapping patterns like the red black tree balance pattern this means exponential code size.

For such patterns where none of the actions involve recur we could implement backtracking with a pre-allocated exception.

http://blogs.oracle.com/jrose/entry/longjumps_considered_inexpensive



 Comments   
Comment by David Nolen [ 28/Sep/11 10:46 PM ]

Fixed now in master.

Generated at Mon Sep 01 18:25:11 CDT 2014 using JIRA 4.4#649-r158309.