On Sunday, 6 December 2015 at 03:24:24 UTC, Timon Gehr wrote:
> Some upper bounds are incomparable, so there would not be a total order. But that is not a problem.

It is a problem in all cases as you usually dont have an optimal bound. And with your approach that will most certainly be guaranteed to happen. Comparing bounds does not mean you are comparing running time.

O(1) implies O(f(x)), O(N) implies O(N^2).

You can also get tighter bounds for specific input models.

On 12/06/2015 08:59 AM, Ola Fosheim Grøstad wrote:
> On Sunday, 6 December 2015 at 03:24:24 UTC, Timon Gehr wrote:
>> Some upper bounds are incomparable, so there would not be a total
>> order. But that is not a problem.
>
> It is a problem in all cases as you usually dont have an optimal bound.

Are you complaining that the given implementation does not support 'min', or what are you trying to say here?

> And with your approach that will most certainly be guaranteed to happen.

How is that specific to my approach? I only showed a more expressive BigO implementation.

> Comparing bounds does not mean you are comparing running time.
> ...

BigO represents a set of functions. Comparing BigO checks for subset inclusion.

> O(1) implies O(f(x)), O(N) implies O(N^2).
>

For our purposes, O(f) = { g | ∃c. ∀x⃗. |g(x⃗)| ≤ c·|f(x⃗)|+c }.

O(1) ⊆ O(f(x)), O(N) ⊆ O(N²).

<= checks ⊆.
== checks =.

(The final implementation should use exact fractions instead of doubles.)

> You can also get tighter bounds for specific input models.
>

Yes, you can.

On 12/06/2015 03:39 PM, Timon Gehr wrote:
>
> For our purposes, O(f) = { g | ∃c. ∀x⃗. |g(x⃗)| ≤ c·|f(x⃗)|+c }.

Hm, this does not actually work too well. E.g., we want

O(n+m) ⊆ O(n log m + m log n).

This breaks down with that definition if we e.g. fix m=1 and let n vary.

Anyway, I think this can be fixed.

Timon Gehr <timon.gehr@gmx.ch> wrote:
> On 12/05/2015 09:48 PM, Andrei Alexandrescu wrote:
>> On 12/04/2015 10:24 PM, Timon Gehr wrote:
>>> void foo(@(BigO.linear) int n,@(BigO.linear) int m);
>>> 
>>> But UDAs for parameters are not supported.
>> 
>> That's actually pretty neat and easy to work around like this:
>> 
>> void foo(int n, int m) @(BigOParam!2(BigO.linear, BigO.linear);
>> 
>> In fact I went through the implementation but soon I hit a wall: what's the _relationship_ between the two growths? It may be the sum O(m + n) but also the product O(m * n). So the operator must be encoded as well.
>> 
>> Then what do we do with more complex relationships like O((m + n) log n)
>> etc.
>> 
>> Then once you get to some reasonable formula, what's the ordering on top
>> of these complexities? Probably difficult.
>> ...
> 
> Some upper bounds are incomparable, so there would not be a total order. But that is not a problem.
> 
>> I gave up on this for the time being. Ideas welcome.
>> ...
> 
> The next step up the expressiveness scale would be to have a sum-of-products representation.
> 
> Proof of concept (disclaimer: hacked together in the middle of the night, and not tested thoroughly):
> 
> http://dpaste.dzfl.pl/d1512905accd
> 
> I think this general approach is probably close to the sweet spot. (The implementation is not feature-complete yet, though. It would be nice if it supported automatically computing a new asymptotic runtime bound from asymptotic bounds on the arguments.)
> 

Brilliant! My wife has a work emergency so I've been with the kids all day, but here's what can be done to make this simpler.

Use D parsing and eliminate the whole parsing routine. Add multiply and power are all defined so you only need log of bigo.

Define global constants K, N, and N1 through N7. K is constant complexity all others are free variables.

Then complexities are regular D expressions e.g BigO(N^2 * log(N)).

On a the phone sry typos.

On Sunday, 6 December 2015 at 14:39:05 UTC, Timon Gehr wrote:
> Are you complaining that the given implementation does not support 'min', or what are you trying to say here?

I am saying that comparing bounds is not the same as comparing running time of implemented algorithms. Insertion sort is both O(n^2) and O(n^3), but if you run it on a sorted array where each element have been swapped with neighbouring elements 16 times, then it is O(N).

So these derived bounds are too loose to be useful, generic algorithms cannot make use of them beyond the trivial case.

> BigO represents a set of functions. Comparing BigO checks for subset inclusion.

But what can you use it for? When you compose algorithms and even run an optimizer over it, then combining a O(N^2) with O(N) kan turn into O(1). You need advanced compiler support for this to be valuable.

>> You can also get tighter bounds for specific input models.
>>
>
> Yes, you can.

Exactly, and when you compose/combine algorithms you often end up constraining the input model.

On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
>> >
>> >The next step up the expressiveness scale would be to have a
>> >sum-of-products representation.
>> >
>> >Proof of concept (disclaimer: hacked together in the middle of the
>> >night, and not tested thoroughly):
>> >
>> >http://dpaste.dzfl.pl/d1512905accd
>> >
>> >I think this general approach is probably close to the sweet spot. ...
>> >
> Brilliant! My wife has a work emergency so I've been with the kids all day,
> but here's what can be done to make this simpler.
>
> Use D parsing and eliminate the whole parsing routine. Add multiply and
> power are all defined so you only need log of bigo.
> ...

The implementation of power on BigO given does not actually work in general (there should have been an enforcement that makes sure there is only one summand). I'll think about whether and how it can be made to work for multiple summands.

> Define global constants K, N, and N1 through N7. K is constant complexity
> all others are free variables.
>
> Then complexities are regular D expressions e.g BigO(N^2 * log(N)).
>
> On a the phone sry typos.

I generally tend to avoid DSLs based solely on operator overloading, as they don't always work and hence are awkward to evolve. Here, the biggest current nuisance is that the variable names are not very descriptive. If we'll go with a log(BigO) function, we possibly want to make BigO closed under log without approximating iterated logarithms:

struct Term{
    Variable n;
    Fraction[] exponents; // exponents[0] is exponent of n,
                          // exponents[1] is exponent of log n,
                          // exponents[2] is exponent of log log n, ...
}

Then O(log(f^c*g^d)) = O(log(f)+log(g)) = O(log(f+g)) [1], and hence every BigO has a well-defined logarithm.


[1] O(log(f+g)) ⊆ O(log(f*g)) = O(log(f)+log(g)).
    O(log(f)+log(g)) ⊆ O(max(log(f),log(g)))
                     = O(log(max(f,g)))
                     ⊆ O(log(f+g)).

On 12/06/2015 10:35 PM, Ola Fosheim Grøstad wrote:
> On Sunday, 6 December 2015 at 14:39:05 UTC, Timon Gehr wrote:
>> Are you complaining that the given implementation does not support
>> 'min', or what are you trying to say here?
>
> I am saying that comparing bounds is not the same as comparing running
> time of implemented algorithms.

Yes, that's what you said later down the post. It's completely unrelated to the sentence you claimed was false.

On Sunday, 6 December 2015 at 23:49:00 UTC, Timon Gehr wrote:
> Yes, that's what you said later down the post. It's completely unrelated to the sentence you claimed was false.

i would assume that there would have to be a usecase for something added to a standard library. Based on the presented use case it is like using the classifications "younger than 100" and "younger than 16", apply them randomly to indivduals of the same age and use the classifications for making decisions about whether they should be allowed to see adult movies or not. Putting an ordering on the classification is in that case useless.

On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
>> >The next step up the expressiveness scale would be to have a
>> >sum-of-products representation.
>> >
>> >Proof of concept (disclaimer: hacked together in the middle of the
>> >night, and not tested thoroughly):
>> >
>> >http://dpaste.dzfl.pl/d1512905accd
>> >
>> >I think this general approach is probably close to the sweet spot. ...
>> >
> Brilliant! ...

I have noticed another thing. The comparison operator is an underapproximation (it sometimes returns NaN when ordering would actually be possible).

E.g., O(n·m) ⊆ O(n²+m²), because n·m ≤ n²+m².

Interesting. It would be nice if the final version had a complete decision procedure for ⊆.

On 12/06/2015 06:21 PM, Timon Gehr wrote:
> The implementation of power on BigO given does not actually work in
> general (there should have been an enforcement that makes sure there is
> only one summand). I'll think about whether and how it can be made to
> work for multiple summands.

No matter, you may always use runtime assertions - after all it's all during compilation. That's the beauty of it!

>> Define global constants K, N, and N1 through N7. K is constant complexity
>> all others are free variables.
>>
>> Then complexities are regular D expressions e.g BigO(N^2 * log(N)).
>>
>> On a the phone sry typos.
>
> I generally tend to avoid DSLs based solely on operator overloading, as
> they don't always work and hence are awkward to evolve. Here, the
> biggest current nuisance is that the variable names are not very
> descriptive.

The bright side is you get to standardize names. If you limit names to K, N, and N1 through N7 then you can always impose to APIs the meaning of these.

Another bright side is people don't need to learn a new, juuust slightly different grammar for complexity expressions - just use D. For example the grammar you defined allows log n without parens - what's the priority of log compared to power etc? Why is power ^ in this notation and ^^ in D? All these differences without a distinction are gratuitous. Just use D.

> If we'll go with a log(BigO) function, we possibly want to
> make BigO closed under log without approximating iterated logarithms:
>
> struct Term{
>      Variable n;
>      Fraction[] exponents; // exponents[0] is exponent of n,
>                            // exponents[1] is exponent of log n,
>                            // exponents[2] is exponent of log log n, ...
> }
>
> Then O(log(f^c*g^d)) = O(log(f)+log(g)) = O(log(f+g)) [1], and hence
> every BigO has a well-defined logarithm.
>
>
> [1] O(log(f+g)) ⊆ O(log(f*g)) = O(log(f)+log(g)).
>      O(log(f)+log(g)) ⊆ O(max(log(f),log(g)))
>                       = O(log(max(f,g)))
>                       ⊆ O(log(f+g)).

Yah, the stuff under log must be restricted. Here's the grammar I'm toying with:

Atom ::= K | N | N1 | ... | N7
SimpleExp ::= SimpleTerm ('+' SimpleTerm)*
SimpleTerm ::= SimpleFactor ('*' SimpleFactor)*
SimpleFactor ::= Atom ('^^' double)? | '(' SimpleExp ')'
BigO ::= Term ('+' Term)*
Term ::= SimpleFactor ('*' 'log' '(' SimpleExp ')' ('^^' double)?)?

(I used regex notations for "optional" and "zero or more".)

This is expressible with D's native operations (so no need for custom parsing) and covers, I think, what we need. It could be further simplified if we move some of the grammar's restrictions to runtime (e.g. no need for SimpleXxx, some expressions can be forced to be simple during "runtime").


Andrei