[armedbear-devel] Performance improvement special binding read/write
Last weekend, I ran Maxima tests since some time again. I don't remember the older performance figures, although I remember the total test suite - possibly performance tuned - to take 3300seconds before. Last weekend, it was 3900seconds, giving me a feeling of performance regression. So I decided to take another look. I found two things, one of which is that we still have slow special binding value lookup. Peter Graves suggested some time ago that we switch to the same scheme used by SBCL and CCL because he found that XCL benefitted ~10% on his tests when he made the same switch. The scheme used by SBCL/CCL differs from the one used by ABCL in the way the "active" binding is being accessed. ABCL manages all bindings as a linked list, with the most recent one as the active one. This means O(n) access time on the number of special bindings. In SBCL/CCL, the active binding is stored in an array, with a linked list to record which values to restore when unwinding the binding. Upon restore, this solution takes more cycles than our solution: we simply change the head of the linked list, whereas the SBCL/CCL solution needs to set all the array elements. Running the application which we know tests special bindings performance the best [Maxima], I see a strong performance improvement: 3900 seconds before and 2300 seconds after the change. Performance improved by ~40%! I'll commit this change after cleaning up. Bye, Erik.
Committed in r12275. Bye, Erik. On Tue, Nov 10, 2009 at 2:38 PM, Erik Huelsmann <ehuels@gmail.com> wrote:
Last weekend, I ran Maxima tests since some time again. I don't remember the older performance figures, although I remember the total test suite - possibly performance tuned - to take 3300seconds before. Last weekend, it was 3900seconds, giving me a feeling of performance regression. So I decided to take another look.
I found two things, one of which is that we still have slow special binding value lookup. Peter Graves suggested some time ago that we switch to the same scheme used by SBCL and CCL because he found that XCL benefitted ~10% on his tests when he made the same switch.
The scheme used by SBCL/CCL differs from the one used by ABCL in the way the "active" binding is being accessed. ABCL manages all bindings as a linked list, with the most recent one as the active one. This means O(n) access time on the number of special bindings.
In SBCL/CCL, the active binding is stored in an array, with a linked list to record which values to restore when unwinding the binding. Upon restore, this solution takes more cycles than our solution: we simply change the head of the linked list, whereas the SBCL/CCL solution needs to set all the array elements.
Running the application which we know tests special bindings performance the best [Maxima], I see a strong performance improvement: 3900 seconds before and 2300 seconds after the change. Performance improved by ~40%!
I'll commit this change after cleaning up.
Bye,
Erik.
participants (1)
-
Erik Huelsmann