Self Optimizing Code

[Mark J Twain via Digitalmars-d]

On Thursday, 4 August 2016 at 11:35:41 UTC, crimaniak wrote:
> On Tuesday, 2 August 2016 at 22:06:38 UTC, Mark "J" Twain wrote:
>> Instead, a better solution would be to use variables:
>>
>> if (n*length > m*capacity) expand(l*length)
>
> Some time ago I played with self-optimizing cache layer.
> Problem: Time to obtain cache items is unknown and server 
> dependant. For example, network can be involved in this. 
> Sometimes is it localhost, sometimes server on another 
> continent. Time to cache it is unknown too. For example if 
> memcached extension is not installed on this server then 
> fallback to disk backend will slow cache performance very much. 
> So we don't know is it worst to cache.
> Solution: cache measures own performance and acts accordingly.
>

I did not think of this in terms of networking. I suppose it can 
be used there too but, as you mention, latency could be a factor.

> So I make next things:
> 1. Functional interface instead of save/load type interface. 
> cacheLevel.get(functor_to_get_item) allow to measure item 
> obtaining time.
> 2. Implement all measuring/controlling logic in separate class 
> with interface AbstractStatist, in CacheLevel class make just 
> hooks for it. So changing AbstractStatist implementation I can 
> change work mode to measure statistics and use it or work as 
> usual cache (EmptyStatist for all empty hooks). I make 
> implementation to skip all items not worst caching 
> (calcTime/calcHits*totalHits-totalTime < 0) but it's possible 
> to make more smart things (like caching only most efficient 
> items not exceeding cache size).

If it is more complex, that what I described, it would have to be 
thought out a great deal. My goal was to simply have the program 
expose optimization points(variables) then allow an optimizer to 
change those to find better points. The program itself would be 
virtually unmodified. No code to interact with the optimization 
process except to use variables instead of constants(which is 
minimal and necessary).

Exposing an interface for the program itself to guide the 
optimization process seems like a lot more work. But, of course, 
ultimately is better as it allows more information to flow in to 
the optimization process. But this design is beyond what I'm 
willing to achieve(this way could be months or years to get done 
right), while my method could take just a few hours to code up, 
and is rather general, although a bit dumb(fire and forget and 
hope for the best).

> In my experience I can draw some conclusions.
> 1. It need to separate measure mode and control mode. You can't 
> have accurate statistics while changing system behavior 
> according to current statistics state.
> 2. Statistics can be different for different applications but 
> for specific application in specific conditions for most cases 
> it can be approximated as constant.
>

Yes, it is tricky to make the algorithm stable. This is why I 
think, for a simple optimizer, it would need to do this over long 
periods(months of program use). Because there are so many 
aberrations(other programs, user behavior, etc), these can only 
be statically removed by repetitive uses. Essentially "low pass 
the data to remove all the spikes" then compare the avg result 
with the previous.


> So for array allocating strategy more realistic scenario the 
> next, I think:
> 1. Application compiled in some 'array_debug' mode then some 
> statist trait added to array, collect usage statistics and 
> writes optimal constants at the application exit.
> 2. Programmer configure array allocator in application 
> according to these constants.
> 3. Application builds in release mode with optimal allocation 
> strategy and without any statist overhead and works fast. Users 
> are happy.

This is more static profiling type of optimizations. I am talking 
about something a bit different.  Both methods could be used 
together for a better result, but mine is for simplicity.  We 
generally blindly set constants for things that affect 
performance. Let's simply turn those constants in to variables 
and let a global blind optimizer try to figure out better values 
than what we "blindly" set. There is no guarantee that it would 
find a better result and may even introduce program instability. 
But all this stuff can be somewhat measured by cpu and memory 
usage and given enough parameters, there is probably at least 
several optimal points the optimizer could find.

Ultimately for just a little work(setting the variables and 
specifying their ranges and step, say), we could have most 
programs being created, in D for now at least, optimizing 
themselves(while they are being used by the user after they have 
been shipped) to some degree.  This, I believe, is unheard of. It 
represents the next level in program optimizations.

Imagine one day where a program could optimize itself depending 
on the hardware of the user, the users habits, etc. Well, this 
method attempts to get that ball rolling and does all those 
things in a general way(albeit ignorant, but maybe just as 
effective). It's hard to know how effective until it is done, but 
we do know it can't be any worse than what we already have.