forum.alglib.net

ALGLIB forum
It is currently Wed Aug 15, 2018 7:18 am

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Coding of the "rcomm" routines.
PostPosted: Sat Dec 02, 2017 9:36 pm 
Offline

Joined: Mon Nov 20, 2017 11:14 pm
Posts: 8
I noticed that in the ALGLIB source, about 20-25 routines (the "two-way communication" routines) have had their control flow structures completely atomized. I'm not sure if you're aware that C and C++ permit jumps into and out of control flow structures, and that it was not actually necessary to tear apart the control flow structures.

In the local version of ALGLIB, I have restored them all -- about a year ago -- with a slight increase in performance and the resulting discovery of orphan code in various points, that had been left behind from earlier versions. I have done the same with the mcsrch routine (which apparently is legacy from an earlier FORTRAN edition, particularly one which made use of the language's former ability to have multiple entry points).

The general format I use is as follows:

A "pause" at "stage" N with the "need" flag F raised:
... F = true, stage = N; goto Pause; ResumeN: F = false; ...
This may sit inside the middle of a for-loop or other control flow structure.

A "spawn" at the start of the routine:
if (stage >= 0) goto Resume;
Spawn:
Initialize only those variables randomly that are not initialized before the first "Pause" or "Exit"
star the routine.

An "exit" to end the routine:
goto Exit;
with the label
Exit: return false;

A label to "pause" the routine:
Pause:
Save the live "thread local" variables
return true;

A label to "resume" the routine:
Resume:
Retrieve the live "thread local" variables
switch (stage) { case 0: goto Resume0; case 1: goto Resume1; ... }
drop down into Exit if none of the cases apply.

The main body, however, keeps its control flow structures intact. This makes it much easier to analysis and maintain. In particular, it make much easier to do diff-patches between versions.


Top
 Profile  
 
 Post subject: Re: Coding of the "rcomm" routines.
PostPosted: Tue Dec 05, 2017 2:59 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 825
Hi!

Thank you for the suggestion! I agree that it will make code more maintainable. And you gave an interesting point on performance - case/switch based solution is indeed expected to be faster than the sequence of if/then.

However, there are two reasons why this code existed for so long in ALGLIB for C++:

1. I was already aware of the fact that C/C++ standard allows jumps into control structures. The fact I am unaware of is the following: how many widely used compilers adhere to this standard in such fine details? Obviously, GCC, MSVC, ICC. But we have several industry users who continue to use many years old compilers for obscure systems... and I afraid that some of these compilers may break.

I know that you and me are right :) but I afraid that something may break even if we are right. And ALGLIB tries to be as portable as possible. If you can add something on this point, I'd be glad to hear it!


2. A bit demotivating is the fact that ALGLIB for C# can not be optimized in the similar way.

Although C# has support for continuations, some fine details are slightly different. Continuations do not match 100% to reverse communication interface. So, utilizing C# native continuations opens the door for potential mismatch between ALGLIB for C++ and ALGLIB for C#. Code which behaves differently in C++ and C# versions. And, unfortunately, C# does not allows us to switch into the middle of the control structure - its switch/case statement is quite limited.

So, even if we fix C++, C# control structures will still be blown apart. It is not the reason to abandon C/C++ improvements - but it is demotivating factor.


Top
 Profile  
 
 Post subject: Re: Coding of the "rcomm" routines.
PostPosted: Wed May 16, 2018 11:14 pm 
Offline

Joined: Mon Nov 20, 2017 11:14 pm
Posts: 8
In reply to the question "Something to add?" Yes: I have actual code for the modifications in the free C++ version, validated by the test routines.

Generally speaking, there was no problem since the original/intended structure is predictable from the pattern of the labels (you kept in redundant labels intact that mark the original control flow structures). The only place I ran into a problem was trying to "optimize" out the comparisons in the logistic routine, where I initially failed to realize that you're using infinitesimals in the routine. That was easily fixed.

But I also redid the Fortran-legacy pause-resume code in my copy, which apparently predates your "rcomm" routines; notably mcsrch -- the routine with the old-style Fortran comments still in it.

If nothing else, by examining the revised code, you'll be in a better position to do an analysis of the variables to determine what needs to be retained and/or saved across thread-switches. Usually, most or all the variables can be made local, leaving only a few that needs to be saved.

In general, whatever revisions I made goes to straight into the test routines for validation; so as to eliminate 90-95% of any debugging activity. A change of as much as 10,000-20,000 lines can usually be validated (with errors searched for and corrected) by these means in a few hours at most; with the search mostly automated. This is why I strongly suggest distributing the package with a testing/validation makefile (if nothing else, it gives users an example to work off of). The time stamp of the most recently passed test run then serves as a "version number" for the local copy.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC


Who is online

Users browsing this forum: Bing [Bot] and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group