issue-#72 speeding up the dump of large data structures

issue-#72 speeding up the dump of large data structures

Postby Josef Templ » Tue Sep 29, 2015 1:25 pm

This issue is about an optimization in the generation of the post mortem dump of large data structures,
in particular for large arrays allocated on the stack. If such an array contains structured elements
(arrays or records) this involves a large number of StdFold.Flip operations, which in turn call the
TextModels.StdContext.Pos operation several times. The TextModels.StdContext.Pos operation
uses a linear search and the resulting runtime behavior is quadratic.

For the issue see http://redmine.blackboxframework.org/issues/72.

A proposal for a fix exists in CPC 1.7 rc5.
However, the proposal has several drawbacks.
It uses a separate stack for avoiding the Flip operation. This stack has a fixed size and thereby
is too large in most cases and too small in the extreme case of very deeply nested data structures.
The stack is also hard to understand but in principle it works.

Note that there is no need for such a stack because of the recursive
structure of the dump procedures. The stack can be maintained easily
inside the recursive dump procedures which is simpler to read and avoids a fixed
size auxiliary stack.

For the changes based on the pproposal in CPC 1.7 rc5 but without an explicit stack see http://redmine.blackboxframework.org/projects/blackbox/repository/diff?utf8=%E2%9C%93&rev=19f8cf554cb056a21ddf1a9dc3eaed7a64dcb2d5&rev_to=7a4042a068896e7fd55c347b2d76fc3cd5beae40.

- Josef
User avatar
Josef Templ
 
Posts: 2003
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#72 speeding up the dump of large data structures

Postby DGDanforth » Sun Oct 04, 2015 11:28 am

I notice the string
Code: Select all
"   "
occurs 16 times (8 times in each module). I would think a better approach
following the rule "one place only" would be to define,
Code: Select all
CONST spacer = "   "

and use
Code: Select all
spacer
for those occurrences.

-Doug
User avatar
DGDanforth
 
Posts: 1061
Joined: Tue Sep 17, 2013 1:16 am
Location: Palo Alto, California, USA

Re: issue-#72 speeding up the dump of large data structures

Postby Josef Templ » Mon Oct 05, 2015 5:40 am

> I notice the string " " occurs 16 times (8 times in each module).

Certainly true, but not related to THIS issue.
It can be changed in an attempt of beautifying the sources such as in
CPC 1.7 rc5 change list number 22 (changes by Trurl), which contain
lots of similar beautifications.

- Josef
User avatar
Josef Templ
 
Posts: 2003
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#72 speeding up the dump of large data structures

Postby Zinn » Wed Oct 07, 2015 4:18 pm

Josef, your solution is perfect and better as the one in CPC.
I think, it is ready for voting on it.
- Helmut
Zinn
 
Posts: 470
Joined: Tue Mar 25, 2014 5:56 pm
Location: Frankfurt am Main

Re: issue-#72 speeding up the dump of large data structures

Postby Josef Templ » Wed Oct 07, 2015 4:39 pm

Thanks, Helmut. Just go ahead with the voting.
User avatar
Josef Templ
 
Posts: 2003
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#72 speeding up the dump of large data structures

Postby Ivan Denisov » Sun Oct 18, 2015 9:20 am

I found the description in Russian and now I am understanding the problem better!
http://forum.oberoncore.ru/viewtopic.ph ... 740#p75740

Ilya gave there the example of test code.
Code: Select all
MODULE TestDo;
   IMPORT  Log, Math;
   PROCEDURE Test*;
   VAR dat: ARRAY 4096 OF ARRAY 2 OF ARRAY 2 OF INTEGER;
   BEGIN
   HALT(0)
   END Test;
END TestDo.Test


So I compared the time before and after this fix. I used version:
http://blackboxframework.org/unstable/i ... a1.239.zip
With fix it takes only 3-4 seconds to build the TRAP window, without fix it takes 30-40 sec!

I was abstaining from voting, because did not understand the issue well. Now all is clear and I am changing my voice from Abstain to Yes.
Ivan Denisov
 
Posts: 1694
Joined: Tue Sep 17, 2013 12:21 am
Location: Russia


Return to Resolved (Bugs)

Who is online

Users browsing this forum: No registered users and 3 guests

cron