F.init(x, a)

[B Saunders]

While trying to build a test, I got a compiler error concerning ambiguous signatures for ring/field element init in one of the Modular fields.  Examining init definitions I found extensive and inconsistent sets of signatures for init.  Note that not just lack of a signature is a problem.  Too much is also problematic here, due to the ambiguity.  I attach a file showing the Modular<T>::init signatures.

My second attachment is a test program illustrating that a compiler will happily do implicit conversions to double from all the primitive numeric types when the signatures on offer are double and Integer.   For the test I used Givaro::Modular<int8_t> but commented out all init(Element&, const T&) except for T = double and Integer.  [...also redefined init(... double) to avoid an infinite regress.] 

I propose we define just the two signatures double and Integer for Element inits in each field/ring class.  The thought is to have double for efficiency and exactitude in most cases and have Integer for exactitude in all cases.

Best,
-dave

[Alexis Breust]

Hello dave,

So, using just the double/integer interface will implicitly convert long long to double?
Should I then cast it myself to an integer before calling init: init(a, integer(k)); to be sure I loose no precision?

Anyhow, I like the idea, of having a clean init interface.

Best,
Alexis.

[B Saunders]

Yes, I had in mind to not require getting the full range of long long.

One gets full range using integer and convenience with small values using double.

However, in the meantime I've resolved the ambiguity at the caller (a LinBox test) by explicit cast to double.

I wouldn't mind full support 64 bit int, but use int64_t rather than long long.

Incidentally, this is the behavior I want for init/convert on finite rings and polynomial rings over finite rings.

For Field::Element e, f, and integer i,j or (double i,j and F.cardinality() < 2^52)

F.areEqual(e, init(f, convert(i, e))) // init composed with convert is identity on F.

Init is a bijection of  0..F.cardinality() - 1 to F (for finite ring)

Init is also a bijection of 0.. F.characteristic()-1 to the prime subfield of F, with 

init(e, i) having the property that e = F.one added i times.

When the ring is finite and i >= 0,

convert(j, init(e, i)) == i % F.cardinality()

I don't specify a generic meaning for init from a negative integer.  In particular, I don't require

F.areEqual(F.mOne, init(e, -1)).  I note that this is tested for in Givaro/tests/test-ffarith.

I propose that individual fields/rings can choose their own behavior on negative integers.

Best,
-dave

--
Prof. B. David Saunders, 302-831-6238, CIS Department, University of Delaware

--
You received this message because you are subscribed to the Google Groups "linbox-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to linbox-devel...@googlegroups.com.
To post to this group, send email to linbox...@googlegroups.com.
Visit this group at http://groups.google.com/group/linbox-devel.
For more options, visit https://groups.google.com/d/optout.

[Clement Pernet]

init and converts are indeed supposed to be morphisms from/to any other domain, satisfying some
composition condition: init(convert(x))=x.

Any field has to define at least one morphism from Integers, but I strongly disagree with the idea
that it should be the only one: we do not want to pay the price of a cast to Integer or even to
double in order to convert an int16_t to an int64_t.

One should allow fields to define any pair of such morphisms and let the prorammer of such fields be
in charge of avoiding ambiguity.

Le 29/05/2015 02:57, B Saunders a écrit :
> Incidentally, this is the behavior I want for init/convert on finite rings and polynomial rings over
> finite rings.
> For Field::Element e, f, and integer i,j or (double i,j and F.cardinality() < 2^52)
> F.areEqual(e, init(f, convert(i, e))) // init composed with convert is identity on F.
>
> Init is a bijection of 0..F.cardinality() - 1 to F (for finite ring)

Ok with that

>
> Init is also a bijection of 0.. F.characteristic()-1 to the prime subfield of F, with
> init(e, i) having the property that e = F.one added i times.

This is a too strong requirement. For example, this is not compatible with the use of Kronecker
substitutions (i.e. evaluate a polynomial in an element) to convert a field extension to integers.

More generally, we always hit the same design issue: we implicitely assume that the type of the
second arg to an init defines the semantic of how elements are represented over this type.

Maybe init/convert still have a too wide usage and we should
1/ restrict it to what Dave proposed: a canonical integer representation of elements, with
init/converts from/to Integer only.
2/ create morphisms outside the definition of a field, templated by the InField and OutField
Example:

Morphism < Givaro::GFqDom<int>, ZRing<double> > (const int src, double& dest);

What do you think?

Clément

>
> When the ring is finite and i >= 0,
> convert(j, init(e, i)) == i % F.cardinality()
>
> I don't specify a generic meaning for init from a negative integer. In particular, I don't require
> F.areEqual(F.mOne, init(e, -1)). I note that this is tested for in Givaro/tests/test-ffarith.
> I propose that individual fields/rings can choose their own behavior on negative integers.
>
>
> Best,
> -dave
>
> --
> Prof. B. David Saunders, 302-831-6238, CIS Department, University of Delaware
>
> On Tue, May 26, 2015 at 10:38 AM, Alexis Breust <alexis...@gmail.com
> <mailto:alexis...@gmail.com>> wrote:
>
> Hello dave,
>
> So, using just the double/integer interface will implicitly convert long long to double?
> Should I then cast it myself to an integer before calling init: init(a, integer(k)); to be sure
> I loose no precision?
>
> Anyhow, I like the idea, of having a clean init interface.
>
> Best,
> Alexis.
>
> --
> You received this message because you are subscribed to the Google Groups "linbox-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to

> linbox-devel...@googlegroups.com <mailto:linbox-devel...@googlegroups.com>.

> To post to this group, send email to linbox...@googlegroups.com

> <mailto:linbox...@googlegroups.com>.

> Visit this group at http://groups.google.com/group/linbox-devel.
> For more options, visit https://groups.google.com/d/optout.
>
>

> --
> You received this message because you are subscribed to the Google Groups "linbox-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to

> linbox-devel...@googlegroups.com <mailto:linbox-devel...@googlegroups.com>.

> To post to this group, send email to linbox...@googlegroups.com

> <mailto:linbox...@googlegroups.com>.

[B Saunders]

I don't make opinion or argument in this email, just report on some study of the uses of init and convert.

Study of convert:

I found a little over one hundred calls to convert in LinBox, mostly in algorithms/.  Of those 96 calls in algorithms/, all were converting to integer except a half dozen to double.  No other type receives the conversion.

In fflas I found again convert to integer and double (and sometimes to double in disguise as Givaro::DoubleDomain::Element).  Also a few perhaps to float as in

template<class FloatElement ...> ... { ... FloatElement tmp; F.convert(tmp, x); ...}

(OK.  I don't know for sure if FloatElement is meant to sometimes be an int type or not.)

And a few where the range of expected types is less clear to me:
template<class Field ...
            typename MMHelper<Field, AlgoT, ModeCategories::LazyTag >::DFElt al;
            F.convert(al, alpha);

I didn't survey Givaro.  There I would see the use in Kronecker substitution...

Study of init:

I attach the 168 uses of init in LinBox/tests/ (other than F.init(x) calls).

One case is "F.init(alpha, alpha)"!   In the context, the author expects a prime field and is using init to perform remainder modulo the characteristic, I believe.  Other cases involve init from literal integer and floating values both positive and negative.  Some are from index variables of various types such as int and size_t.  I'm pretty sure that on some of these calls and with some fields, init() is not doing what the caller expects. 

For this type of "casual" use of init, we could encourage explicit casts on literals and on variables of type subject to uncertain implicit conversion.

Best,
-dave

--
Prof. B. David Saunders, 302-831-6238, CIS Department, University of Delaware

To unsubscribe from this group and stop receiving emails from it, send an email to linbox-devel...@googlegroups.com.
To post to this group, send email to linbox...@googlegroups.com.

[Alexis Breust]

Isn't it possible to make a "struct Element { int64_t rep; }"
instead of a "typename int64_t Element" that makes things are to differentiate?
I joined a file like illustrates that.

Not sure that it could solve all issues but it certainly helps semantically.

[B Saunders]

The linbox field::Element design is carefully crafted to allow primitive types for elements.  This is to avoid a significant performance overhead when using such wrappers as you describe.  Perhaps it is worth a check to see if compilers have evolved to the point of being able to blow away the overhead.  If so, it would be revolutionary.  My bet is the overhead is still too great.

Best,
-dave

[Gavin Harrison]

I wrote a simple test:

version 1:

void square(std::vector<struct Element> a) {

    for (int i = 0; i < a.size(); i++)

        a[i].rep *= a[i].rep;

}

version 2:

void square(std::vector<int> a) {

    for (int i = 0; i < a.size(); i++)

        a[i] *= a[i];

}

The diff of the output (g++ -O3 -s test*.cpp) is:

1c1

< .file "test.cpp"

---

> .file "test2.cpp"

7,9c7,9

< .globl _Z6squareSt6vectorI7ElementSaIS0_EE

< .type _Z6squareSt6vectorI7ElementSaIS0_EE, @function

< _Z6squareSt6vectorI7ElementSaIS0_EE:

---

> .globl _Z6squareSt6vectorIiSaIiEE

> .type _Z6squareSt6vectorIiSaIiEE, @function

> _Z6squareSt6vectorIiSaIiEE:

140c140

< .size _Z6squareSt6vectorI7ElementSaIS0_EE, .-_Z6squareSt6vectorI7ElementSaIS0_EE

---

> .size _Z6squareSt6vectorIiSaIiEE, .-_Z6squareSt6vectorIiSaIiEE

So, the only difference is the mangled type names.

Gavin

[Alexis Breust]

@Gavin Harrison
The idea was that the classic user would use F.assign(c, a); if a is a properly initialized Element.
F.init(c, a.rep); is for internal use with accumulation, the developer knows that a.rep needs to be reduced.

+@Dave
I made a test (joined) and compiled with:
g++ -S -O3 -std=c++11 overhead-wrapper.cpp -DDIRECT -o wrapper-direct.asm
g++ -S -O3 -std=c++11 overhead-wrapper.cpp -o wrapper-indirect.asm
The only difference are order of instructions but they are the same.

22,23d21

< movdqa %xmm2, %xmm0

< addl $1, %eax

24a23,24

> addl $1, %eax

> movdqa %xmm4, %xmm0

26,28d25

< paddd %xmm6, %xmm2

< pmuludq %xmm4, %xmm0

< pshufd $8, %xmm0, %xmm0

31a29,31

> pmuludq %xmm2, %xmm0

> pshufd $8, %xmm0, %xmm0

> paddd %xmm6, %xmm2

[B Saunders]

Gavin, Alexis,

I've heard this attributed to Kernighan about unix: "simple things should be easy, complicated things should be possible".  The corresponding slogan about generated code performance that compilers seem to follow is "simple code should be compiled well, complicated code should be compiled somehow."

LinBox asks compilers to do complicated things.

Best,
-dave

--
Prof. B. David Saunders, 302-831-6238, CIS Department, University of Delaware

[Clement Pernet]

Ok, thanks Gavin & Alexis for your 2 examples.

I'm still wondering how this can be put in practice for fflas-ffpack matrices, i.e. Element* with a
stride parameter lda.

We should be able to write code transparently on these Element* matrices, and avoid double pointer
indirection.
Gavin experiment seem to show that this is the case with std::vectors, but what about arrays
(allocate by a new Element[N])?

Clément
PS: note that we recently (last summer) changed all Element* by some typedefs Element_ptr for a
related topic: in all fields but one, the 2 types are equivalent, but for the RNS elements, the
pointer arithmetic is overloaded to handle a 2nd stride to navigate in the multimodular basis.

If one can adopt this new system, this would make things much simpler, but I'm still not convinced
that it is doable.

[Gavin Harrison]

Dave,

I know struct in C++ can mean something that has class like behavior, but if struct is used as it would in C, as an alias for a primitive type (or collection of primitive types), then I don't know how it is more complicated than aliasing those types by using typedef.  It is a pretty sweeping change to all of the three libraries. The upside is it would protect against some types of mistakes.

Clément,

Here's the diff I get when I change vector<T> to T* for T = int or struct Element, and add an int n param for the loop bound:

1c1
< .file "test.cpp"
---
> .file "test2.cpp"
7,9c7,9

< .globl _Z6squareP7Elementi
< .type _Z6squareP7Elementi, @function
< _Z6squareP7Elementi:
---
> .globl _Z6squarePii
> .type _Z6squarePii, @function
> _Z6squarePii:
126c126
< .size _Z6squareP7Elementi, .-_Z6squareP7Elementi
---
> .size _Z6squarePii, .-_Z6squarePii

Gavin

[Gavin Harrison]

Hi All,

After some research, it seems that the C++ standards body has gone through some pain to describe in what instances a struct will laid out as in C (for purposes of communicating between languages and optimization), and will be treated like Plain Old Data (POD).  I found a thorough explanation on Stack Exchange here.

Thanks,

Gavin

PS - Link in case it doesn't work in body.

link: http://stackoverflow.com/questions/4178175/what-are-aggregates-and-pods-and-how-why-are-they-special/7189821#7189821

[B Saunders]

POD layout:  Interesting.  However to convince me c11 gets there would take:

(1) build field rep Modular<wrapped<int32_t> >

(2) compare with Modular<int32_t> in field benchmarks and in uses in a variety of Linbox solution benchmarks.  ...and with a variety of compilers.

I was going to add (3) and this is not worth your time.  Now I'm not so sure of that part.  A remaining question is whether the compiler will inline functions as completely as it must for us.

Best,
-dave

--

You received this message because you are subscribed to the Google Groups "linbox-devel" group.

To unsubscribe from this group and stop receiving emails from it, send an email to linbox-devel...@googlegroups.com.
To post to this group, send email to linbox...@googlegroups.com.

[Gavin Harrison]

Hi All,

I spent some time and actually tried it.  I added givaro/ring/modular-wrapped-int32.h and linbox/field/Modular/modular-wrapped-int32.h.  I moved the various givaro modular int macros into the bodies of the functions, but later added overloaded operators for the wrapper (to satisfy fflas), which I should have done at the start.  I got linbox/test/test-det to compile using the wrapped version in place of plain int32 implementation.  It passes the givaro ffarith and linbox det tests.

I had roughly the same performance using both versions compiling with -O3 -flto and running ./test-det - -n 200.  I can't commit to givaro, so I just bundled up my working directory and linked it below if anyone wants to take a look.

Thanks,

Gavin

link: https://drive.google.com/open?id=0B1yttdpLR5_dcjJGQi1yT1NVeTA&authuser=0

[B Saunders]

On Wed, Jun 3, 2015 at 10:02 AM, Clement Pernet <clement...@gmail.com> wrote:

init and converts are indeed supposed to be morphisms from/to any other domain, satisfying some
composition condition: init(convert(x))=x.

Any field has to define at least one morphism from Integers, but I strongly disagree with the idea
that it should be the only one: we do not want to pay the price of a cast to Integer or even to
double in order to convert an int16_t to an int64_t.

I  can't identify any code where we init a bunch of int16_t's into a field...   Meanwhile I observe many definitions of init that are just wrappers on a cast (to long, to long long, to int64_t, etc.).  In short, I see baggage in the code base  that is causing compilation ambiguities and is a candidate for cleanup...  Still I'd like to honor this goal of efficiency.

One should allow fields to define any pair of such morphisms and let the prorammer of such fields be
in charge of avoiding ambiguity.

The main problem, I think, is that we try to make init/convert meet too many distinct goals (modular reduction, Kronecker substitution, element-to-index, i/o pickling).  Thus even the most generic init/convert from/to Integer has conflicting demands.  A field designer can't use init/convert from/to Integer for both modular reduction and Kronecker substitution, so support of multiple morphisms based on type alone isn't sufficient...

EVERY commutative ring is a Z-module via the "natural" map: For elements x, y and intType n, we have zmul (y, n, x) returns y = x + .. + x (n times).

Every CR1 has a natural projection from the integers, nat (x, n) returns x = 1 + .. + 1 (n times).

These modular reduction maps are universal.  I propose we introduce nat() and/or zmul().  Nat() could be specified to allow x be uninitialized, thus in effect doing the job of many current calls to init.  Regarding the ambiguities that arise from implicit typecasts, we could probably agree on using just a few int types here.

This frees up init/convert to support Kronecker substitution, mapping to/from indices (= Kronecker substitution of cardinality for x), i/o pickling.  

One place where I can't decide just what to do is in gfq.  There I see init used for Kronecker substitution of specifically a power of 2.  The map-to-index is also wanted.  I can see a solution that costs an extra branch in init() or a solution that reserves an int type to the map-to-index use (int32_t perhaps).

-dave

Le 29/05/2015 02:57, B Saunders a écrit :
> Incidentally, this is the behavior I want for init/convert on finite rings and polynomial rings over
> finite rings.
> For Field::Element e, f, and integer i,j or (double i,j and F.cardinality() < 2^52)
> F.areEqual(e, init(f, convert(i, e))) // init composed with convert is identity on F.
>
> Init is a bijection of  0..F.cardinality() - 1 to F (for finite ring)

Ok with that

>
> Init is also a bijection of 0.. F.characteristic()-1 to the prime subfield of F, with
> init(e, i) having the property that e = F.one added i times.

This is a too strong requirement. For example, this is not compatible with the use of Kronecker
substitutions (i.e. evaluate a polynomial in an element) to convert a field extension to integers.

Isn't your concern the other way?  For Kronecker substitution, even nested substitution, I think the elements of the prime subfield map to 0..p-1 (or perhaps to -p/2..p/2).  Whereas, my desire for a bijection, field elements -> 0,,cardinality(), IS in conflict with Kronecker sub.  By the way, this mapping is wanted for an application where field elements index matrix rows (and I think it is useful, though not required, for i/o).

Anyway, I am amenable to a carefully type (init function signature) driven semantics.  Users, including the 168 calls in linbox tests, should be explicit about type.  

Here is a thought:

EVERY ring is a Z module via the natural mapping nat: n -> 1 + 1 + ... + 1 (n times).  So we introduce the function

    Elt & F.nat(Elt & x, const intType & n) 

User can write F.nat(two, 2) instead of F.init(two, 2)

Possibly we also have zmul(Elt x, intType n, Elt y) which computes mul(x, nat(z, n), y).  

This simplifies the discussion of init/convert to the support of Kronecker sub, map to index, and i/o uses.  Those are actually all compatible if we allow one of the cases for Kronecker substitution to be evaluation at p = characteristic. 

Vis a vis Kronecker:  Does an extra argument to init and convert serve the need: convert(intType n, Elt f, intType base) = f(base)?  BTW, what types do you really want for this use?  integer for sure.  double?  int64_t?  Not much demand for small types, I'd assume.

 

More generally, we always hit the same design issue: we implicitely assume that the type of the
second arg to an init defines the semantic of how elements are represented over this type.

Maybe init/convert still have a too wide usage and we should
1/ restrict it to what Dave proposed: a canonical integer representation of elements, with
init/converts from/to Integer only.
2/ create morphisms outside the definition of a field, templated by the InField and OutField
Example:

Morphism < Givaro::GFqDom<int>, ZRing<double> > (const int src, double& dest);

What do you think?

Not sure yet.  My remarks above suggest some variant more or less.  Here is one comment:

We have Hom<R1, R2> intended to support the algebraically clear morphisms of projection(Z->Z_p), injection(F->Ext(F)), isomorphism(change of rep).

The morphisms that init/convert deal in are algebraically partial, thus harder to specify clearly. 

a) Kronecker substitution: commutes with arithmetic to a limited extent.

b) i/o: just need bijection to some subset of Z, no algebraic morph preserved. (Arguably, this use need not be supported.  Field element read/write can be independent of init/convert)

c) matrix indexing by element over GF(p^e):  need bijection to 0..p^e-1.  Compatible with Kronecker for base = p.

For example, I'm not sure I could write a good spec for ZRing<double>, much less for a morphism to it.

This related to my desire to provably get from BLAS what we assume and observe in practice.

To unsubscribe from this group and stop receiving emails from it, send an email to linbox-devel...@googlegroups.com.
To post to this group, send email to linbox...@googlegroups.com.