Re: Efficient Sequential Access to Arrays

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Mon, 16 Jul 2012 12:12:48 -0700 (PDT), Keean Schupke wrote:

> On Monday, 16 July 2012 19:48:22 UTC+1, Dmitry A. Kazakov  wrote:
>> On Mon, 16 Jul 2012 09:39:45 -0700 (PDT), Keean Schupke wrote:
>> 
>> > On Monday, 16 July 2012 15:57:04 UTC+1, Dmitry A. Kazakov  wrote:
>> 
>> >> Which itself looks like a problem. It takes no less than 25% of overall
>> >> performance for mere shuffling data in a task unrelated to stuff like
>> >> recoding etc. This looks wrong to me. I would look for a better
>> >> algorithm/structure.
>> > 
>> > I find this comment puzzling and does not match my experience.
>> 
>> It is just an observation that more than 25% of CPU load is spent to heat
>> the atmosphere rather than doing something useful.
>> 
>> > What algorithm for disjoint-set do you suggest I use?
>> 
>> I would try to avoid using such things if the problem is large.
> 
> Perhaps you would like to outline your methodology for algorithm
> development?

I don't develop algorithms I apply them.

25% overhead on indexing is too much.

> How would you go about designing an efficient algorithm to
> solve these kind of problems:
> 
> 嚙瘟 Network connectivity.

1. Open amazon site
2. Search "netwok adapter" 
3. Choose 5 different with minimal price
4. Among them select one with maximal positive customer reports
5. Buy it

(Network connectivity is not an algorithmic problem)

>> No idea what you are trying to do. But indexing *must* be faster than
>> indirection. You should make your data structures straight.
> 
> Straight data structures require copying data. If we were to use an array
> instead of a linked list then every state change would require copying
> stuff.

In Ada you rename array elements. This lets the compiler to choose between
copying and handling it in-place. BTW copying might turn more effective
depending on the architecture.

>> >> If you have performance problems with arrays, which are built-in and
>> >> subject of tailored optimization, you cannot expect situation improved by
>> >> puzzling the compiler with more abstract types. That could only disable
>> >> optimization.
>> > 
>> > Maybe you are thinking of something more complex than I am. An ADT is just
>> > a private type with associated functions in a package.
>> 
>> It is difficult for the compiler to optimize wrappers of array operations
>> like indexing. You said you failed to make GCC to optimize raw array
>> access. Why wrapping that into functions should do any better?
> 
> It doesn't do any worse... the functions are mostly single line and get
> inlined before the optimisation pass.

Did you verify that?

> On the whole many positives, and no negatives (because its just as fast in my tests).

But you said you failed to optimize multiplication away.

>> > Element's is different from the STL. It includes native 'concepts' that
>> > define axiomatic constraints on software modules.
>> 
>> I have no idea what "axiomatic constraints on software modules" could mean.
> 
> See:
> 
> http://akrzemi1.wordpress.com/2012/01/11/concept-axioms-what-for/

Ah, you meant invariants, propositions regarding program semantics
maintained true during code transformations, e.g. for optimization.

In more complex cases user could help the compiler giving some advices. But
for low-level optimizations like ones of indexing this stuff is buried in
the compiler guts.

However, yes, Ada should have interfaces of integer types, interfaces of
index types, interfaces of array types etc, annotated by
pre-/post-conditions and invariants. Unfortunately, presently interfaces
are tied with by-reference types. It is unclear when Ada will provide
interfaces for all types. Otherwise, regarding program correctness stuff
there is SPARK and some in Ada 2012.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de