These are chat archives for symengine/symengine

17th
Jun 2015
Sumith Kulal
@Sumith1896
Jun 17 2015 08:15
I get following error when I am trying to use piranha::term
/home/sumith/github/csympy/src/dict.h:30:27: error: ‘term’ is not a member of ‘piranha’
 typedef piranha::hash_set<piranha::term<unsigned long long, piranha::integer>> hash_set;
                           ^
/home/sumith/github/csympy/src/dict.h:30:27: error: ‘term’ is not a member of ‘piranha’
Sumith Kulal
@Sumith1896
Jun 17 2015 08:50
piranha::hash_set used with term as std::pair works fine. I am doing something wrong with the piranha::term syntax.
Sumith Kulal
@Sumith1896
Jun 17 2015 09:17

I got the new poly_mul3 working with

typedef std::unordered_set<std::pair<unsigned long long, unsigned long long>,
            boost::hash< std::pair<unsigned long long, unsigned long long> >> hash_set;

the above data structure

To have a good comparison with Piranha, we need to use piranha::integer, piranha::termand piranha::hash_set
@certik @bluescarni
Abinash Meher
@abinashmeher999
Jun 17 2015 09:44
@isuruf @certik
The build jobs for -DWITH_RUBY="yes" failed here: https://travis-ci.org/sympy/symengine/builds/67144020
I had deleted extconf.rb, the only place where RbConfig was used, still it shows error related to RbConfig. Saying that Config is deprecated and suggesting to use RbConfig instead. Errors are different for different versions of Ruby.
In one case, it can't find the header file cwrapper.h.
Isuru Fernando
@isuruf
Jun 17 2015 09:52
I'm not sure about this language feature.
Language of the project is cpp, but all workers include Ruby 1.9.3, that's why only the version with Ruby 1.9.3 actually tries to build
cwrapper.h error is due to not including cwrapper.h in src/ruby/lib/symengine/CMakeLists.txt
Btw, you can enable travis-ci to your repo
Abinash Meher
@abinashmeher999
Jun 17 2015 09:56
https://travis-ci.org/sympy/symengine/jobs/67144051
This log is a little peculiar. At the beginning it shows version 2.2.0 with the command ruby --version. Where as here at https://travis-ci.org/sympy/symengine/jobs/67144051#L325, it shows that found version is 1.8.0
Shall I enable it? Then all future (the near future) the wrappers will be tested only from my repo. So if anyone wants to contribute, he/she will have to contribute to my repo first.
Or shall I move this to a new repo, like the julia wrappers?
Isuru Fernando
@isuruf
Jun 17 2015 10:02
No, I just meant, if you enable travis-ci to your repo, all tests will be run in your repo as well. (sympy/symengine might have a queue and it might be quicker to run in your repo)
Take a look at how we manage Python versions.
We introduce a variable PYTHON_VERSION and if it is set, we install the python version we need. You could do the same
Abinash Meher
@abinashmeher999
Jun 17 2015 10:05
Oh, I get it now. I can do that. Only that, managing many languages gets a little confusing. So, I will be enabling travis for ruby_file_structure, right? I will have to modify the .travis.yml in that case, specifying the name of my branch.
Isuru Fernando
@isuruf
Jun 17 2015 10:06
No need. Just enable tests in travis-ci.org and all branches will be built as changes are pushed
Abinash Meher
@abinashmeher999
Jun 17 2015 10:07
Ok. That's convenient.
Isuru Fernando
@isuruf
Jun 17 2015 11:27

@certik, @sushant-hiray I was able to build cmake on sage on OSX 10.10 after patching CMake. (I'll send a patch to CMake). Only 6 out of 387 tests fail. Can you check as well?
https://github.com/isuruf/sage/tree/cmake

CMake source is here, ​http://www.cmake.org/files/v3.2/cmake-3.2.1.tar.gz. (Put it in upstream folder)

Francesco Biscani
@bluescarni
Jun 17 2015 11:53
@Sumith1896 you should probably use hash_set with a pair, the term stuff is for representing specifically polynomials, but hash_set can store any type of object
Think of hash_set as, more or less, a drop-in replacement for std::unordered_set
Sumith Kulal
@Sumith1896
Jun 17 2015 11:54
Okay, I thought term was also an drop-in replacement for pair!
Francesco Biscani
@bluescarni
Jun 17 2015 11:54
the use of piranha::term is not important for performance
it is essentially very similar to a pair, it's a pair with some extra stuff in
Sumith Kulal
@Sumith1896
Jun 17 2015 11:55
Let me try
Francesco Biscani
@bluescarni
Jun 17 2015 11:55
but you don't need that extra stuff
Sumith Kulal
@Sumith1896
Jun 17 2015 11:55
So I can remove the boost hash right?
Francesco Biscani
@bluescarni
Jun 17 2015 11:56
I am not totally sure if C++11 has support for std::hash of a generic pair
but if it does not, it's not difficult to provide it
Sumith Kulal
@Sumith1896
Jun 17 2015 11:56
I had to provide it for std::pair
Francesco Biscani
@bluescarni
Jun 17 2015 11:56
hash_set defaults to std::hash for hashing
ahh I see
I understand probably boost hash just combines the hashes of the two members of the pair
so it should be enough to get started
Sumith Kulal
@Sumith1896
Jun 17 2015 12:00
Yes combines

When I use

typedef piranha::hash_set<std::pair<unsigned long long, piranha::integer>> hash_set;

I get the following error

(open the link if you are not able to read)
Francesco Biscani
@bluescarni
Jun 17 2015 12:04
This should be because std::hash is not defined for std::pair. Try passing in boost::hash as second template parameter (same way you did for std::unorered_set)
Sumith Kulal
@Sumith1896
Jun 17 2015 12:07
Yes, if I use boost hash I get this
/usr/include/boost/functional/hash/extensions.hpp:201:24: note:   template argument deduction/substitution failed:
/usr/include/boost/functional/hash/extensions.hpp:269:34: note:   ‘const piranha::mp_integer<>’ is not derived from ‘const std::unique_ptr<_Tp, _Dp>’
             return hash_value(val);
Maybe because piranha::integer is our type, not std
Francesco Biscani
@bluescarni
Jun 17 2015 12:07
ahh right... now you have the problem that boost::hash does not know about piranha's integer
yep
so here is what you can do
you need to specialise std::hash
let me dig it out for you
you need to replace custom_string with std::pair<long long, integer>
and change the implementation of the call operator of the structure
to use hash_combine
so the body of the operator would look something like this:
std::size_t retval = 0;
hash_combine(retval,std::hash<unsigned long long>()(p.first));
hash_combine(retval,std::hash<piranha::integer>()(p.second));
return retval;
here p is an instance of std::pair<long long, integer>
Francesco Biscani
@bluescarni
Jun 17 2015 12:16
something likes this in the end:
(untested)
you must place this outside any namespace (piranha, symengine or otherwise)
Sumith Kulal
@Sumith1896
Jun 17 2015 12:19
Is the hash_combine from boost?
Francesco Biscani
@bluescarni
Jun 17 2015 12:19
yes
forgot about that
as a matter of fact, probably you don't even need to combine the hashes... in a polynomial you care only about the monomial part for hashing right?
for identifying specific terms in the polynomial, e.g., during multiplication
Francesco Biscani
@bluescarni
Jun 17 2015 12:26
hashing only the monomial part would be simpler:
Sumith Kulal
@Sumith1896
Jun 17 2015 12:29
Sorry, I went off for a bit
Trying this out
Error again
/usr/local/include/piranha/hash_set.hpp: In instantiation of ‘class piranha::hash_set<std::pair<long long unsigned int, piranha::mp_integer<> >, std::hash<std::pair<long long unsigned int, piranha::mp_integer<> > > >’:
/home/sumith/github/csympy/src/rings.cpp:117:10:   required from here
/usr/local/include/piranha/hash_set.hpp:107:3: error: static assertion failed: type trait check failure -> is_hash_function_object<Hash,T>
   PIRANHA_TT_CHECK(is_hash_function_object,Hash,T);
   ^
make[2]: *** [src/CMakeFiles/symengine.dir/rings.cpp.o] Error 1
make[1]: *** [src/CMakeFiles/symengine.dir/all] Error 2
Francesco Biscani
@bluescarni
Jun 17 2015 12:31
add a noexcept at the end, after const in the call operator
Sumith Kulal
@Sumith1896
Jun 17 2015 12:31
Okay
Francesco Biscani
@bluescarni
Jun 17 2015 12:32
mhm not sure actually if it fixes it.. can you post the code somewhere?
Sumith Kulal
@Sumith1896
Jun 17 2015 12:33
Looks like the file compiles with that fix
I'll post the code in a bit once the compilation stops
Should have posted earlier, I forgot
Francesco Biscani
@bluescarni
Jun 17 2015 12:33
ok... is this piranha from hashstack?
Sumith Kulal
@Sumith1896
Jun 17 2015 12:34
My Piranha is a git clone, if that's what you are asking
Francesco Biscani
@bluescarni
Jun 17 2015 12:35
ok, I thought I removed that noexcept check at some point... is it the master branch, and from when?
Sumith Kulal
@Sumith1896
Jun 17 2015 12:37
It is a old version, maybe March or so
I don't exactly remember the last time I pulled from master
Isuru Fernando
@isuruf
Jun 17 2015 12:37

@abinashmeher999, disregard my comments at https://gitter.im/sympy/symengine?at=5581459ddeac73ee5b85749d

Your method is fine. Only problem is ruby version installed by rvm is not picked by the script bin/test_travis.sh

Francesco Biscani
@bluescarni
Jun 17 2015 12:37
ok cool.. that noexcept thing is gone now
Sumith Kulal
@Sumith1896
Jun 17 2015 12:40
Ohh boy, it is very slow
maybe my routine is messed up
Code is here: Sumith1896/csympy@bab90bb
The poly_mul3 uses hash_set
Are we sure about the hash?
The speeds are down to 3800ms
Francesco Biscani
@bluescarni
Jun 17 2015 12:42
can you print the final size of the polynomial?
Sumith Kulal
@Sumith1896
Jun 17 2015 12:42
No. of terms you mean?
Francesco Biscani
@bluescarni
Jun 17 2015 12:42
yes
or the size of the hash set
Sumith Kulal
@Sumith1896
Jun 17 2015 12:42
It's 6272
Francesco Biscani
@bluescarni
Jun 17 2015 12:42
if you prefer
so the correct number is coming out when you run the code?
Sumith Kulal
@Sumith1896
Jun 17 2015 12:43
Yeah
Francesco Biscani
@bluescarni
Jun 17 2015 12:44
ok because there is probably something wrong with the equality operator
so when you work with hashing containers
you need to make sure that the hashing and the equality predicate are consistent
in this case, we are storing monomials-coefficient pairs
and using only the monomial part for hashing
which makes sense, right? because during multiplication you want to accumulate terms with equal monomial part
not store them separately
but the hash set is using the standard equality predicate right now
std::equal_to
which is going to compare both part of the pair, including the coefficient
so you have an inconsistency, because the hashing is done only on the monomial
but the comparison operator takes into account the coefficient as well
if you see here, the equality operator for pair examines both elements of the pair
so we need to pass a custom equality operator to hash_set (or to unordered_set, it would be the same thing)
Sumith Kulal
@Sumith1896
Jun 17 2015 12:48
To just check the first, that is monomial?
Francesco Biscani
@bluescarni
Jun 17 2015 12:49
yes precisely
I don't know if that fixes the performance, but it is something that needs to be dealt with
right now the comparison operator is comparing also the coefficients
the integer coeffcients, I mean
which is much slower than just comparing the hardware ints making up the monomials
Sumith Kulal
@Sumith1896
Jun 17 2015 12:51
The overriding should be done same as we did for hash, right?
Francesco Biscani
@bluescarni
Jun 17 2015 12:51
in this case it's probably better to create just an outside functor and use it
for hash there was not a default implementation defined for std::pair
but for std::equal_to there is one
so better to keep them separate
(creating a gist)
something like this should work
Sumith Kulal
@Sumith1896
Jun 17 2015 12:56
Yes let me try this, we have done something like this for SymEngine before
@bluescarni Better now, 98ms
But not what we expected, right?
Francesco Biscani
@bluescarni
Jun 17 2015 13:01
right, it should be a few times faster right?
Sumith Kulal
@Sumith1896
Jun 17 2015 13:01
Yeah we were expecting to reach close Piranha
This is the poly_mul3 routine
void poly_mul3(const hash_set &A, const hash_set &B, hash_set &C)
{   
    std::pair<unsigned long long, piranha::integer> temp;
    for (auto &a: A) {
        for (auto &b: B) {
            temp.first = a.first + b.first;
            temp.second = a.second*b.second;
            C.insert(temp);
        }
    }
}
I think there is a better way to do this.
Francesco Biscani
@bluescarni
Jun 17 2015 13:02
yep looking right now... I have a question though
Sumith Kulal
@Sumith1896
Jun 17 2015 13:03
Go on
Francesco Biscani
@bluescarni
Jun 17 2015 13:03
here you are doing a straight up insert in the set, but shouldn't you be checking if the term is already there?
Sumith Kulal
@Sumith1896
Jun 17 2015 13:05
Ohh right I cant do it this way, can I?
Why is the no.of terms coming out right?
Francesco Biscani
@bluescarni
Jun 17 2015 13:06
the number of terms will still be ok, but you are replacing an existing monomial with another one each time you do the insert
instead of adding the coefficient to the existing term's coefficient
Sumith Kulal
@Sumith1896
Jun 17 2015 13:07
Right, so I'll have to check
Francesco Biscani
@bluescarni
Jun 17 2015 13:07
shouldn't matter much for perf though
Sumith Kulal
@Sumith1896
Jun 17 2015 13:07
Give me couple of minutes
Won't the checks matter?
Francesco Biscani
@bluescarni
Jun 17 2015 13:07
ok.. for performance we might check a few other things
the insert() method first does a lookup in the set anyway
but all this won't (or shouldn't) change the performance much
just the correctness of the result
Sumith Kulal
@Sumith1896
Jun 17 2015 13:09
Okay, any views on why it is slow?
Francesco Biscani
@bluescarni
Jun 17 2015 13:10
I don't see annything obvious at the moment, we should probably inspect the resulting hash_set to see if something fishy is going on
like, most elements are confined in a few buckets instead of being spread out on the table
this could happen if the hashing is not good, which in turn might depend on how the kronecker codification is implemented
but let's not put the ox ahead of the cart :)
Sumith Kulal
@Sumith1896
Jun 17 2015 13:12
Should I try out with hash_combine of Boost?
Worth a shot
Francesco Biscani
@bluescarni
Jun 17 2015 13:12
we need to diagnose the problem first
Sumith Kulal
@Sumith1896
Jun 17 2015 13:13
Yes, any checks I can perform from my side?
Francesco Biscani
@bluescarni
Jun 17 2015 13:14
yes you can do something like this on the resulting hash set (give me a sec)
So I do not know if the evaluate_sparsity() method is available in older Piranha versions
this code snippet will print to screen a series of numbers, like:
0,1234
1,567
2,12
this means that there are 1234 empty buckets
567 buckets with 1 element
12 buckets with 2 elements
in a healthy table most items will be in buckets with a single element
if there's something fishy with the hashing, you will have buckets with lots of elements in them
Francesco Biscani
@bluescarni
Jun 17 2015 13:22
right looks we have found one problem at least :)
how is the kronecker packing implemented?
my guess would be you are using bit shifting/masking
Francesco Biscani
@bluescarni
Jun 17 2015 13:31
this is what I am getting in Piranha for the expand2b test:
Ondřej Čertík
@certik
Jun 17 2015 13:56
@bluescarni thanks a lot for all the help! So it looks like our hash function is screwed up.
@isuruf I'll try your cmake, hopefully today or tomorrow.
Isuru Fernando
@isuruf
Jun 17 2015 13:57
Thanks
Francesco Biscani
@bluescarni
Jun 17 2015 13:58
@certik no problem
I had similar problems in the past, so I have some hints on what might go wrong and how to fix it
just dumping them here:
Ondřej Čertík
@certik
Jun 17 2015 13:59
@abinashmeher999 this looks like a bug in our CMake. So this should be easy to fix.
It's probably out of the tree build issue.
Francesco Biscani
@bluescarni
Jun 17 2015 13:59
hash_set uses power-of-two sizes, for performance reason. The first thing is then to make sure that the hashing does not proceeds by power of two or anything of the sort
secondly, when you implement kronecker size, you must make sure that you are producing long ints that spread out as much as possible
kronecker size -> kronecker codification
if your kronecker codification produces values in a limited range of the long int type, you might run into issues
it's the same with any hash function really
in piranha I produce the kronecker values by multiplying the exponents by randomly-selected prime numbers
in an effort to produce kronecker values which are little composite as possible
Ondřej Čertík
@certik
Jun 17 2015 14:02
@bluescarni I understand the mechanism with prime numbers that you spread out the ints, but I don't understand why. Shouldn't the hash function of ints take care of this?
Francesco Biscani
@bluescarni
Jun 17 2015 14:03
the hash function for primitive types typically just takes the int and casts it to std::size_t
python does that as well I think
Isuru Fernando
@isuruf
Jun 17 2015 14:05
@abinashmeher999, FindRuby.cmake used in cmake-2.8 (which is what we use in travis) is too old. That's why there is a problem in version.
Francesco Biscani
@bluescarni
Jun 17 2015 14:07
I think the problem with the specific usage of hash_set discussed here might have to do more with the power of two thing though, more than spreading and prime numbers
that's my hunch anyway
Ondřej Čertík
@certik
Jun 17 2015 14:07
@bluescarni I see. Why do you need to spread the hash function though? I thought as long as it gives different numbers to different ints, it should be fine, wouldn't it?
I see why --- because you take the hash and do modulo the size of the hashtable, is that right? And we need to make sure it is spread out in the actual hashtable.
Francesco Biscani
@bluescarni
Jun 17 2015 14:10
@certik it's been a while since I thought about all this, but I think the idea is that if you have a very large table and ints which are not as much spread out, then you will use only the lower buckets. Which might be fine if you are storing few elements, but not good if you have many
yes
Ondřej Čertík
@certik
Jun 17 2015 14:11
As to power of two, does hash_set increase its size in powers of two? What exactly do you need to do with the hash to make this performing well?
Francesco Biscani
@bluescarni
Jun 17 2015 14:11
yes, the sizes of the table are 0,1,2,4,8,16,etc.
you need to avoid hashing based on power of two computations
things like bit shifting for instance
Ondřej Čertík
@certik
Jun 17 2015 14:12
I see! Things like this:
//! Part of umap_vec_mpz:
typedef struct
{
    inline std::size_t operator() (const vec_int &k) const {
        std::size_t h = 0;
        for (auto &p: k) {
            h = (h << 4) + p;
        }
        return h;
    }
} vec_int_hash;
Francesco Biscani
@bluescarni
Jun 17 2015 14:13
I would say so yeah
Ondřej Čertík
@certik
Jun 17 2015 14:13
Why don't you increase the hash table based on primes, like other implementations?
I was wondering why they do that, but that's why.
Francesco Biscani
@bluescarni
Jun 17 2015 14:13
because with power of two sizes the reduction of the hash value (the modulo computation) is much faster
it becomes a bitwise operation instead of an integral division
Ondřej Čertík
@certik
Jun 17 2015 14:14
I see. So it's a trade off between the hash function speed versus table lookup speed.
You have to do both anyway each time.
Francesco Biscani
@bluescarni
Jun 17 2015 14:14
I'd say it's more a tradeoff between the hash implementation trickery and the hash function speed
if you take care of avoiding bit shifts in the hash, it will be fine and fast - at least in my experience
I put the primes in the hash function rather than the table size
Abinash Meher
@abinashmeher999
Jun 17 2015 14:20

@isuruf Thanks for looking into it. Is there a way to use a newer version of cmake in travis?
And there are two more problems. I included the ${symengine_BINARY_DIR}/src in CMakeLists.txt in lib/symengine.

include_directories(BEFORE  ${symengine_BINARY_DIR}/src/ruby/ext/symengine
                            ${symengine_BINARY_DIR}/src)

Can't say if that solved the problem. It still can't find cwrapper.h
And the travis running on my fork, cannot find GMP.
https://travis-ci.org/abinashmeher999/symengine/jobs/67183252#L139

Francesco Biscani
@bluescarni
Jun 17 2015 14:21
@certik here's how Java does it:
There's also another thing that is quite crucial: the parallel multiplication algorithm in Piranha needs power of two sizes (something I actually forgot initially)
Abinash Meher
@abinashmeher999
Jun 17 2015 14:23
@certik What is the concept of in-tree builds and out of tree builds? Something related to branch coverage?
Isuru Fernando
@isuruf
Jun 17 2015 14:23
@abinashmeher999, I think we want to keep the cmake version supported 2.8 (@certik, right?). Copy FindRuby.cmake from latest release to symengine repo.
Ondřej Čertík
@certik
Jun 17 2015 14:24
@bluescarni I see, now I understand. You have to put primes in one or the other.
@isuruf if we can support cmake 2.8, that'd be great, since it is the default in Travis.
We want to make it easy for people to install.
Abinash Meher
@abinashmeher999
Jun 17 2015 14:25
@isuruf I am gradually getting what you are trying. That can be done.
This is the one, right?
Sumith Kulal
@Sumith1896
Jun 17 2015 14:28
@certik @bluescarni Sorry my internet goes every couple of hours :smile: Happened the second time today
I hope that gist gave some insight
Looked very fishy to me
Ondřej Čertík
@certik
Jun 17 2015 14:29
@abinashmeher999, @isuruf for what it's worth, I've thrown out the CMake Python's module and wrote my own: https://github.com/sympy/symengine/blob/86d6fce48bcca3edfbf70aa5f855b9e6031786b7/cmake/FindPython.cmake, which is very simple and very robust. CMake tries to be too clever, and it always backfires.
Sumith Kulal
@Sumith1896
Jun 17 2015 14:29
Ohh I see some discussion has happened already
So should I change the way I pack?
Ondřej Čertík
@certik
Jun 17 2015 14:30
@Sumith1896 yes --- pack it the same was as Piranha, add prime numbers (see our discussion above), and then also use the same hash function as Piranha is using --- which I think is just the int itself, if I understand @bluescarni well.
Francesco Biscani
@bluescarni
Jun 17 2015 14:31
yep, just the packed int cast to std::size_t
Isuru Fernando
@isuruf
Jun 17 2015 14:32
@abinashmeher999, instead of include_directories, try this, http://www.cmake.org/cmake/help/v2.8.12/cmake.html#command:target_include_directories
Sumith Kulal
@Sumith1896
Jun 17 2015 14:33
@bluescarni Could you direct me to the packing code and the hash function in Piranha?
Isuru Fernando
@isuruf
Jun 17 2015 14:34
@abinashmeher999, as to your travis-ci tests of your fork, it's because of this,
This job is running on container-based infrastructure, which does not allow use of 'sudo', setuid and setguid executables.
If you require sudo, add 'sudo: required' to your .travis.yml
See http://docs.travis-ci.com/user/workers/container-based-infrastructure/ for details.
Sumith Kulal
@Sumith1896
Jun 17 2015 14:36
Also @certik I hope you looked into poly_mul3, the code is incorrect as of now,
we will have to check before inserting as @bluescarni pointed out
Abinash Meher
@abinashmeher999
Jun 17 2015 14:37
@isuruf But I am using the same .travis.yml. Why a different message?
Isuru Fernando
@isuruf
Jun 17 2015 14:37
Did you activate an education pack in travis-ci.com?
Abinash Meher
@abinashmeher999
Jun 17 2015 14:38
Yes...
Are they related?
Francesco Biscani
@bluescarni
Jun 17 2015 14:39
@Sumith1896 sure give me 5 minutes
Isuru Fernando
@isuruf
Jun 17 2015 14:40
Also, Education Pack users’ builds are routed to this container-based infrastructure.
Abinash Meher
@abinashmeher999
Jun 17 2015 14:42
:sweat:
Why don't I see these? Any workaround?
Isuru Fernando
@isuruf
Jun 17 2015 14:43
Try writing to travis-support and ask them not to route for your open source projects
Speaking of travis support, @certik, shall we request again for OS X support?
Francesco Biscani
@bluescarni
Jun 17 2015 14:45
@Sumith1896 here is an example using Piranha's classes:
https://gist.github.com/bluescarni/795fdaa5750490cddaec
so the kronecker_array class contains static methods to pack vectors of signed ints into a signed integer
Abinash Meher
@abinashmeher999
Jun 17 2015 14:47
Thanks @isuruf @certik ! :smiley: I can't imagine handling these errors without your guidance.
Francesco Biscani
@bluescarni
Jun 17 2015 14:47
you can pass to the encode() method vector-like instances containing a list of integral values that you want to pack into the big signed int
so in the example above, on my machine, the encode of {1,2,3,4,5} produces the value 3344048593939053
Sumith Kulal
@Sumith1896
Jun 17 2015 14:48
So for now, I can used encode method itself right?
See if we reach the speed we want to
Francesco Biscani
@bluescarni
Jun 17 2015 14:49
yes encode() should be enough. It just transforms a sequence of exponents into a single exponent using some stuff involving prime numbers, the details are not important
Sumith Kulal
@Sumith1896
Jun 17 2015 14:49
Cool, let me know
Francesco Biscani
@bluescarni
Jun 17 2015 14:49
you have the corresponding decode() method as well:
Sumith Kulal
@Sumith1896
Jun 17 2015 14:50
Ohh cool, it returns std::vector I assume
Francesco Biscani
@bluescarni
Jun 17 2015 14:51
not precisely, but almost :) let me show you an example
you first need to prepare an output vector out with the appropriate number of elements
then you can decode
Sumith Kulal
@Sumith1896
Jun 17 2015 14:52
Yes, static
Francesco Biscani
@bluescarni
Jun 17 2015 14:52
the decode method needs to know how many values were packed in the int, it cannot know just by inspecting the vector
the long int sorry
it need to ask the size from the vector
yes static
Sumith Kulal
@Sumith1896
Jun 17 2015 14:53
So let me modify things according.
Thanks @bluescarni for all the help. I would have taken ages to figure these out.
Francesco Biscani
@bluescarni
Jun 17 2015 14:54
sure np.. took me ages as well :)
Sumith Kulal
@Sumith1896
Jun 17 2015 15:13
Can I use using ka = kronecker_array<unsigned long long>; in SymEngine code?
Francesco Biscani
@bluescarni
Jun 17 2015 15:15
sure, it's standard C++11 syntax
just an alternative to typedef
just make sure to include the correct header
Sumith Kulal
@Sumith1896
Jun 17 2015 15:19
we do this #include <piranha/piranha.hpp>, that suffices right?
We have included Piranha in CMake
Francesco Biscani
@bluescarni
Jun 17 2015 15:21
yes that should be enough, kronecker_array is part of the public API and should thus be available when you include piranha.hpp
but if you want to reduce compile times you can also include individual pieces of the library
everything that is under src/ can be included on its own
Sumith Kulal
@Sumith1896
Jun 17 2015 15:22
Yes
I am using this using ka = piranha::kronecker_array<unsigned long long> now
Francesco Biscani
@bluescarni
Jun 17 2015 15:24
it needs to be a singed integer, I think like that it will not compile
*signed
you can just do using ka = piranha::kronecker_array<long long> and convert the encoded value to unsigned long long on exit
for now that will do
Sumith Kulal
@Sumith1896
Jun 17 2015 15:25
Okay
Francesco Biscani
@bluescarni
Jun 17 2015 15:25
Piranha is written with Laurent polynomials in mind, so it generally just uses signed quantities for exponentw
*exponents
Sumith Kulal
@Sumith1896
Jun 17 2015 15:26
We too need that in future
Francesco Biscani
@bluescarni
Jun 17 2015 15:30
I'll be gone for a while, will catch you later... if you write something here I will read it eventually
Sumith Kulal
@Sumith1896
Jun 17 2015 15:31
Yes, Thanks again
Sumith Kulal
@Sumith1896
Jun 17 2015 15:42
Cool, there's a speed-up.
Francesco Biscani
@bluescarni
Jun 17 2015 16:39
How's the speedup looking?
Sumith Kulal
@Sumith1896
Jun 17 2015 16:42
24ms now
while expand2c seems to be 33 today
but piranha is still 13.5 - 14ish
But I do have to get it corrected, the poly_mul code
Francesco Biscani
@bluescarni
Jun 17 2015 16:43
did you check about the bucket sparsity?
Sumith Kulal
@Sumith1896
Jun 17 2015 16:43
Only then we should put our report
Francesco Biscani
@bluescarni
Jun 17 2015 16:44
part of performance gap will be gone once you start using the multiply_accumulate functions
and modify the code to use it
Sumith Kulal
@Sumith1896
Jun 17 2015 16:44
0,4399
1,1876
2,1421
3,430
4,66
What is multiply_accumulate, I'm not aware of that?
Francesco Biscani
@bluescarni
Jun 17 2015 16:45
there are also some tricks in hash_set which I can write to you about after the code is fixed
but they require to depart a bit from the interface of unordered_set
basically, when you accumulate the results of term-by-term multiplications you need to often do a coefficient multiplication followed by a coefficient addition
if you generate a new monomial, say 3x23x^2
from the multiplication of xx and 3x3x
and you already have an equivalent monomial in the result C, let's say 6x26x^2
then you need to do the coefficient operations 13+61 * 3 + 6
and the final accumulated result will be 9x29x^2 in C
so it turns out that it's faster to do the multiplication and addition in one pass
this is called an FMA operation (fused multiply add)
it shaves off quite a bit
but it makes sense to do it only after you fixed the poly multiplication routine
as of now you are not doing any addition really, righT?
Sumith Kulal
@Sumith1896
Jun 17 2015 16:50
Yes, I'm on it
I need to serious fix ups now, as even decoding has changed
Previously I had to just add the kronecker key, you see
Francesco Biscani
@bluescarni
Jun 17 2015 16:51
yes, it's good that performance is more reasonable now
Sumith Kulal
@Sumith1896
Jun 17 2015 16:51
Now I have to think of decoding in poly_mul, else mul will go all wrong
Francesco Biscani
@bluescarni
Jun 17 2015 16:53
oh btw
there's another important thing I forgot to tell you about
sorry if I go piece by piece but there's lots of stuff and can't keep it in mind at all times :)
basically Piranha has some code to guess the final size of a polynomial during multiplication
so Piranha can already prepare the hash set with an appropriate number of buckets
this has some important implications for performance
because the way you are doing it now the table is empty, and each time it gets filled up a rehash of all terms is
required
you probably go through 10-15 rehashes with a final polynomial size of 6000
actually more like 13 or so
before starting multiplication, but after you have created C, try to rehash it to a big enough size
C.rehash(10000)
something like this
Isuru Fernando
@isuruf
Jun 17 2015 18:34
Got a reply from cmake about finding libraries here,
http://public.kitware.com/pipermail/cmake/2015-June/060901.html
Ondřej Čertík
@certik
Jun 17 2015 18:37
Yes.
Isuru Fernando
@isuruf
Jun 17 2015 18:39
For packages we can make use of <package>_DIR variable
Ondřej Čertík
@certik
Jun 17 2015 18:42
@bluescarni thanks for all your help. This would take us forever to figure out. @Sumith1896 let's use Piranha classes for now. Hopefully we can figure out how to match Piranha's performance using individual building blocks from Piranha. I think we can just use those in SymEngine and just depend on Piranha for the polynomial module.
Isuru Fernando
@isuruf
Jun 17 2015 18:45
@certik, I don't see a way to achieve the functionality of the macros we defined using CMake variables CMAKE_PREFIX_PATH, CMAKE_INCLUDE_PATH etc
Ondřej Čertík
@certik
Jun 17 2015 18:46
Me neither.

I think if we remove COMMON_DIR as follows:

--- a/cmake/LibFindMacros.cmake
+++ b/cmake/LibFindMacros.cmake
@@ -42,7 +42,6 @@ macro (libfind_library libname pkg)
             ${libname}
         PATHS
             ${${PKG}_DIR}
-            ${COMMON_DIR}
         PATH_SUFFIXES
             lib
             lib64
@@ -73,7 +72,6 @@ macro (libfind_include HEADER pkg)
             ${HEADER}
         PATHS
             ${${PKG}_DIR}
-            ${COMMON_DIR}
         PATH_SUFFIXES
             include
         NO_DEFAULT_PATH

Then we can use CMAKE_PREFIX_PATH, as it will get picked up by the last command (with no NO_DEFAULT_PATH). But for the other functionality, it won't work.

Isuru Fernando
@isuruf
Jun 17 2015 18:51
If there is a library in ${COMMON_DIR}/lib64, it won't be found although that's a rare case.
Ondřej Čertík
@certik
Jun 17 2015 18:52
Right. I just tried it, and CMAKE_PREFIX_PATH seems a reasonable solution for COMMON_DIR. But for the rest, we still need our macros. I am going to reply in this sense to the list.
@isuruf are you on the cmake list?
Isuru Fernando
@isuruf
Jun 17 2015 18:56
yes
Ondřej Čertík
@certik
Jun 17 2015 18:56
ok
Ondřej Čertík
@certik
Jun 17 2015 19:03
@isuruf I just replied.
Abinash Meher
@abinashmeher999
Jun 17 2015 23:22
so I added FindRuby.cmake. But then it showed another error asking about FindPackageHandleStandardArgs.cmake. So I downloaded that too.
Now it is showing this error:
https://gist.github.com/abinashmeher999/554b20680e4430070715
Does this mean, we need to make our own FindRuby.cmake?