forum.alglib.net

ALGLIB forum
It is currently Wed Jun 26, 2019 10:32 pm

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: Incorporation of ALGLIB into a future AI/DSP framework
PostPosted: Tue Mar 19, 2019 8:23 pm 
Offline

Joined: Mon Nov 20, 2017 11:14 pm
Posts: 16
Sergey,

I've posted a few comments over the last year on the design and structuring of the library. Behind these remarks is a longer-term vision and plan that I will describe to you, because it's something that may also be of interest to you and your project.

Over the past few years, I've been closely reviewing your library (the non-commercial C++ version), making numerous tests and revisions of both the routines and core structure to get a better idea of the rationale for its design, the possibility of alternatives and the possibility of expansion with the incorporation of my other software projects -- particularly in the areas of digital signal processing (DSP), and applications in sound, music, video editing and production; as well as natural language processing, advanced computer vision, and other core AI fields of applications.

I have, in fact, recoded the entire library (including the comments) to about 1/3 of its original size, with equal or greater functionality. In its present form, the global state objects have been eliminated (later to be replaced by thread-local objects, if necessary); the _clear() versus _destroy() distinction has been removed, the control flow structures of the rcomm routines have been restored (local variables will later be made thread-local). I might put the function pointers back in, like you had before version 3 or otherwise use lambda abstractions.

Each of the updates you make are incorporated into the rewrite -- including most of the one you just released.

This was the first stage of a series of much deeper restructuring in which it is to be directly written in C++ as a native C++ framework. Feasibility was established last week, when successfully making the transformation on a subset of the library. In the revised form, the distinction between alglib versus alglib_impl is removed; the 3 layers of classes for each object type that you currently have are squashed down to 1 layer, templates are used for vectors and matrices, the _init(), _init_copy() and _clear()/_destroy() routines are directly incorporated into constructor/destructors for the respective types, the global objects that most routines have (particularly those in the optimization and interpolation modules) are generally made into "this" objects; all vestiges of the connection to C is removed.

Much of what you're doing in ap.cpp is already handled by C++ -- particularly shared pools. This library is really meant for C++, rather than C, and the undocumented feature of keeping "alglib_impl" as native C, is hindering its development and maintainability. That I can see clearly now.

With the difficulties I've encountered during this process (particularly that of trying to make this work well with -O{1,2,3} compiler optimization options) it seems like to me that you've probably tried something similar in the past, but ran into problems and that this may be a large part of the rationale behind the extra infrastructure. Any insights you have on this matter I would be interested in hearing.

There are 2 main directions of changes I am taking my local copy of ALGLIB in. First, serialization is to be generalized to include all forms of input/output. It's here that both DSP and codecs may be grafted in. The fast transforms module becomes the core of a DSP module that will include spectral analysis/synthesis, sound morphing, time-frequency transforms, etc. Support for file formats may also be added in alongside the support already existing for strings and streams. Some of the applications that I consider niches of mine ... and ones which will need to make heavy use of both optimization and interpolation modules ... are the automatic extraction of 3 dimensions from photographs and videos (an application of machine learning), reverse-mixing of graphics and sound (an application of non-linear optimization), the power of "X-ray" vision (i.e. the ability to interpolate unseen background behind objects and sounds in a realistic manner: an application of interpolation), the realistic animation of faces and bodies, even from single photos, etc. These are things I can already do to a limited extent. But with your algorithms, this can be taken to a much higher level. The recent changes to spline2d and idw are of particular significance to me in this regard, and this was actually the green light to move forward with everything.

On top of this will be facilities for natural language processing and other AI applications. As a result of these changes, what started out as ALGLIB will transform into a newer and larger library that will also be kept under the GNU license. There will be room for it to be further refined or remade into a multi-threaded and multi-processor framework, but this is not going to be part of the core architecture of the system.

The flagship project for this endeavor is a machine intelligence that will exist, initially only in digital form, but is to be slated for later realization in physical form. It is to be a robot modelled on a close friend; and the expanded framework is being named after her. Sophia, the robot, is going to have company and her name is going to be Lydia. ( https://twitter.com/Lydia_M_W/status/966752545539489792 )

The possibility of the revised framework or its flagship project being later integrated with or into the commercial version is left open as something that should be of interest to you and your company, as these other developments move forward.


Last edited by RockBrentwood on Fri Apr 26, 2019 7:14 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Fixing the FP-comparison vs. optimization bug.
PostPosted: Thu Mar 21, 2019 10:23 pm 
Offline

Joined: Mon Nov 20, 2017 11:14 pm
Posts: 16
An addendum to my remark on integrating ALGLIB into a new library:

"With the difficulties I've encountered during this process (particularly that of trying to make this work well with -O{1,2,3} compiler optimization options) it seems like to me that you've probably tried something similar in the past, but ran into problems and that this may be a large part of the rationale behind the extra infrastructure. Any insights you have on this matter I would be interested in hearing."

is something that you will find of use -- because it's something I see direct mention made of in your comments under the ae_fp_*() fp_*() comparison operations in the ap.* files.

These comparison operations shield against problems that occur when running -O or -O{1,2,3} optimization on the code, because Intel processors use 80-bit internal math, which direct use of is made when the optimizer options are invoked. If the functions are replaced by direct floating-point comparisons, some tests will fail (hqrnd fails; minbleic goes into an infinite loop; minlbfgs behaves differently though it still passes) and other bizarre behavior will occur. The issue of the bad interaction between g++'s optimization and floating point, arising from the fact that Intel uses 80-bit internal math, has been noted in the thread here:

https://stackoverflow.com/questions/7517588/different-floating-point-result-with-optimization-enabled-compiler-bug

where it is suggested to also use the compiler option -ffloat-store, if compiling under g++ with optimization. In the thread, there is also discussion on what compiler options to use with VisualStudio.

I tried it on both my (revised) version of ALGLIB, as well as on the version you distribute ... *after* replacing the functions by direct FP comparisons and everything appears to work fine ... *except* that all the benefits of optimization are lost! The same thing happens if trying to by-pass by the problem by replacing "double" by "long double", if there is not sufficient native support for this type.

Even in a single-threaded environment, the difference between optimizing and not optimizing can be 2.5 to 3 fold; because direct use is made of the FP unit in the former case. So, the loss of the benefits of optimization is significant.

The root of the issue can be seen clearly by #defining the FP operations, e.g.

#define ae_fp_less(A, B) (isnan(A)? (A) < 0.0: isnan(B)? 0.0 < (B): (A) < (B))

This, and similar defines for the other comparison operators, removes all problems (at least -- on my version of GCC). The problem is that the compiler, when optimization is turned on, is not "flushing to zero" its intermediate results. Both that and a fix are described here:

https://www.linuxtopia.org/online_books/an_introduction_to_gcc/gccintro_70.html

The fix is described for the Intel processors: which is to force the CPU's floating point unit to round to double-sized values.

This works with my version of GCC (which is pre-version 5) on an x86. Optimization is not inhibited, FP-comparisons can be made directly without the need for the comparison functions ae_fp_*() or fp_*(), and there is actually a slight speedup overall.

So, the problem should be considered mostly a compiler bug. It is a problem for any compiler that works with the Intel processors, because of the fact that the CPU uses FP registers at non-standard sizes.

Nonetheless, I'm not sure this is entirely 100% a bug in g++'s optimizer.

For instance, hqrnd will pass, if the FP "!=" comparison (that you use the ae_fp_neq() operator for) in the random seed test is replaced by !approxequal() with a suitable threshold (e.g. ae_machineepsilon). The discrepancy between the use of ae_fp_neq() versus a direct "!=" came about because the optimizer coded "!=" directly by the 80-bit FP comparison, but it coded your ae_fp_neq() with IEEE math, as you noted. Under any of the fixes above, this discrepancy is removed, and the need for ae_fp_neq() is removed, as well. But it is still prudent to replace the "!=" by !approxequal() because exact floating point (in-)equality comparisons are not generally considered reliable.

The other places that are affected are minbleic (the feasibility test in particular), minqp, the linreg test (tests that set the grothererrors flag), the mcpd test and the clustering unit restarts test; but it is difficult to trace the exact location where the discrepancies occur. For minbleic, it's probably somewhere inside the mcsrch() function.

But all of the problems here appear to go away when making the above-mentioned fixes. It may also work for other compilers targeting the x86, like VisualStudio.


Top
 Profile  
 
 Post subject: Re: Incorporation of ALGLIB into a future AI/DSP framework
PostPosted: Sun Mar 31, 2019 9:56 pm 
Offline

Joined: Mon Nov 20, 2017 11:14 pm
Posts: 16
Before completing and releasing the revised library, a modified version of the GPL ALGLIB will be released:
* with the structural changes I made to ALGLIB -- which I described here in several contributions
* but without the recoding I described for the Lydia library or any rewording in the comments, other than what was used for the structural changes themselves
This will be announced in a separate note in the next few days.

The modification will be under GPL with the following exceptions:
* the changes made will be separately documented and the specification of the changes will be available for use in the commercial version,
* an explicit provision may also be added to the GPL version to permit the use of any new or changed coding in the commercial version.

Several issues (and bugs) were resolved by the changes made. These are described briefly below
* macros for all the *_init(), *_init_copy(), *_clear(), *_destroy() routines (now called *_init(), *_copy() and *_free()) that encapsulate the data flow of the variables/objects
* macros for the object class declaration and definition code encapsulate these and allow for easy revision
* the object classes were recoded to bring them in line with the {vector/matrix}_wrapper classes: the need for malloc()/free() was eliminated.
* the RCOMM interface was simplified and mostly removed (multi-threaded apps will need to use thread_local declarations)
* the control flow in both the RCOMM routines and legacy FORTRAN routines (e.g. mcsrch()) was restored
* the ALGLIB God-object was removed (ae_state), which will likewise require thread_local declarations for multi-threaded app
* one of the test_x files was altered to reflect the changes (officially, there is no support for multi-threading in the GPL version; but a little of it appears there)
* a makefile with a "make test" was added; specifically configured for GCC/Linux with SSE2 support enabled and -O3 optimization
* -O3 entails a 3-fold speedup and SSE2 support (-msse2 on GCC) entails an addition 2-fold speedup
* the FPU bug for x86/x64 was resolved for GCC/Linux (*NOT* portable), and the FP-comparison functions were all removed.
* the bugs in the calculation of avgce in the dforest module and tester were resolved
Removal of the RCOMM interface and FPU comparison functions, by itself, entailed a 25% speedup in the code ... before SSE2 and -O3 were turned on.

This is an intermediate form between the GPL version of ALGLIB and the newer library "Lydia"; and the changes were preliminary steps geared toward that end. In particular, in the Lydia library, the namespaces will be removed with everything brought into C++, the triple layering of the object classes will be removed, the separate run-time frame will be eliminated in favor of C++'s native run-time frame (thus eliminating most of the need for the locks and other multi-threading hooks), the "self" objects in the API routines (particularly in the Interpolation, DataAnalysis and Optimization) routines being made into "this" ... before the other additions or changes described in the previous note are made.

This is still under development. When completed and distributed, they will also be under GPL, but WITHOUT any exceptions made for the commercial version.

I'm doing this in 2 separate stages like this as a compromise that will make the key structural changes available for both the GPL and commercial versions of ALGLIB, so that Sergey may pick and choose whichever ones he wishes to incorporate into his distribution, without affecting the GPL restrictions to be put on the newer library. And it's being made available for everyone else who wishes to experiment with making and testing their own revisions.


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: Google [Bot] and 1 guest


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