These are chat archives for symengine/symengine

19th
Jun 2015
Sumith Kulal
@Sumith1896
Jun 19 2015 12:28
Hi everyone, due to bad weathers here the internet was down for couple of days.
Sorry, I didn't participate in anything.
Abinash Meher
@abinashmeher999
Jun 19 2015 12:29
Hi @Sumith1896 , nice to have you back.
Francesco Biscani
@bluescarni
Jun 19 2015 12:33
@Sumith1896 welcome back
Sumith Kulal
@Sumith1896
Jun 19 2015 13:07
Thanks @bluescarni @abinashmeher999
Sumith Kulal
@Sumith1896
Jun 19 2015 13:32
I am trying to correct the poly_mul3 routine, a very poor code is here
    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;
            if (C.find(temp) == C.end())
                C.insert(temp);
            else {
                temp.second += C.find(temp)->second;
                C.insert(temp);
            }
        }
    }
Sumith Kulal
@Sumith1896
Jun 19 2015 13:37
I think it can improved much as there are many lookups currently happening, any suggestions?
Sumith Kulal
@Sumith1896
Jun 19 2015 13:47
Wait there is another problem, I'll have to decode
Francesco Biscani
@bluescarni
Jun 19 2015 13:47
@Sumith1896 there's a few things to be fixed, but we'll need to move away from std::pair in order to completely fix the code
but you are right that you can reduce the number of lookups
so the main thing here is that when C.find(temp) != C.end() you will need to modify the .second member of the existing term in C
right? you want to add the coefficient a.second * b.second that you computed above to the existing coefficient already stored in C
but you cannot do that right now, as the iterators in hash_set (just like the iterators in std::unordered_set) give you const access to the element in the array
this makes sense because in general you don't want to mutate existing elements in a set
doing so might, in general, change the hash value of the element
Francesco Biscani
@bluescarni
Jun 19 2015 13:52
so its position within the hash set would be invalidated
Sumith Kulal
@Sumith1896
Jun 19 2015 13:53
But I mutating temp and then inserting
which I assume over-writes
Sumith Kulal
@Sumith1896
Jun 19 2015 13:54
Ooh
I have to move away from std::pair you said?
Francesco Biscani
@bluescarni
Jun 19 2015 13:54
but we gonna fix that :)
Sumith Kulal
@Sumith1896
Jun 19 2015 13:55
What should we do for that?
Francesco Biscani
@bluescarni
Jun 19 2015 13:55
yes.. in our specific case, we know by construction that our hash value depends only on the .first member, right?
Sumith Kulal
@Sumith1896
Jun 19 2015 13:55
Yes, since we have used encode
Francesco Biscani
@bluescarni
Jun 19 2015 13:56
so even if we change the .second member, the position of the existing element in the set will not change
we need to create our own pair that declares the second member as mutable
Sumith Kulal
@Sumith1896
Jun 19 2015 13:57
Then the temp variable can also be eliminated I think
Francesco Biscani
@bluescarni
Jun 19 2015 13:58
partially yes
Sumith Kulal
@Sumith1896
Jun 19 2015 13:59
Also most of the efficiency credits in poly_mul2 was due to
C[a.first + b.first] += a.second*b.second;
that exponent was addition
Francesco Biscani
@bluescarni
Jun 19 2015 13:59
the important thing of the mutable keyword is that it allows to change the value of a member even when the struct is declared as const
yep
Sumith Kulal
@Sumith1896
Jun 19 2015 14:00
Here we have to decode, isn't that an overhead?
Francesco Biscani
@bluescarni
Jun 19 2015 14:00
we don't have to decode during the multiplication
Sumith Kulal
@Sumith1896
Jun 19 2015 14:01
Does adding the encoding integers result in the encode of addition?
Francesco Biscani
@bluescarni
Jun 19 2015 14:01
yes
Sumith Kulal
@Sumith1896
Jun 19 2015 14:01
Cool, I was not aware of that. Not a problem then
Francesco Biscani
@bluescarni
Jun 19 2015 14:01
the addition of the encoded integers results in the encoded addition
Sumith Kulal
@Sumith1896
Jun 19 2015 14:03
So I have to pass my_pair now.
Francesco Biscani
@bluescarni
Jun 19 2015 14:03
yes, let me show you how I would write the mult routine (give me a minute)
something like this (untested)
Sumith Kulal
@Sumith1896
Jun 19 2015 14:16
Yes, this works
Francesco Biscani
@bluescarni
Jun 19 2015 14:17
nice... how's performance looking now?
Sumith Kulal
@Sumith1896
Jun 19 2015 14:17
I used my_pair tweaked hash and eq a bit and passed to hashset and used this poly_mul routine, it compiles
now expand2d is 28-29ms while expand2c is 32-33ms
Improved but not there yet
Francesco Biscani
@bluescarni
Jun 19 2015 14:19
did you notice the thing I wrote a couple of days ago (I think) about rehashing?
Sumith Kulal
@Sumith1896
Jun 19 2015 14:19
Yes, I read a bit but I'll have to re-read
Francesco Biscani
@bluescarni
Jun 19 2015 14:19
basically, try to do C.rehash(10000) before the multiplication loops
Sumith Kulal
@Sumith1896
Jun 19 2015 14:20
Give me a minute to read that message of yours again.
Francesco Biscani
@bluescarni
Jun 19 2015 14:20
sure
Sumith Kulal
@Sumith1896
Jun 19 2015 14:22
Improved to average of 27ms :smile:
Buckets(right word?) distribution has improved I think
0,11488
1,3605
2,1206
3,85
Francesco Biscani
@bluescarni
Jun 19 2015 14:24
mhm ok... let's try something more
try to replace:
it->second += a.second * b.second;
with
piranha::math::multiply_accumulate(it->second,a.second,b.second);
Sumith Kulal
@Sumith1896
Jun 19 2015 14:26
Improved to 23ms :+1:
Nice change
You had mentioned this before I think
Francesco Biscani
@bluescarni
Jun 19 2015 14:27
yes :)
there's still a couple of tricks in Piranha but they are not so easy to implement
but now performance is looking reasonable
Sumith Kulal
@Sumith1896
Jun 19 2015 14:28
expand2c is slower than my previous report from 28ms to 38ms
So getting expand2d to 23ms is good I think
Francesco Biscani
@bluescarni
Jun 19 2015 14:29
was it affected by recent code changes?
Sumith Kulal
@Sumith1896
Jun 19 2015 14:30
brb
I'm afraid yes
Because master is which has just expand2b implemented has times 94ms for expand2b
When we implemented expand2c, I think even expand2b slowed down to 98-ish
Francesco Biscani
@bluescarni
Jun 19 2015 14:34
are you running these benchmarks in a linux machine?
Sumith Kulal
@Sumith1896
Jun 19 2015 14:34
Yes
Francesco Biscani
@bluescarni
Jun 19 2015 14:34
just a heads-up, and I don't know if it changes anything in this case... but
I tend to run benchmarks with sudo nice -n -19 in order to give max priority
and with the system completely at rest
also, if you are on a laptop, dynamic frequency scaling might mess things up from run to run
especially if you are running on battery power
Sumith Kulal
@Sumith1896
Jun 19 2015 14:36
Oh, I'll keep these in mind
Francesco Biscani
@bluescarni
Jun 19 2015 14:37
just FYI, getting a computer to run at max speed can be tricky nowadays :)
Sumith Kulal
@Sumith1896
Jun 19 2015 14:37
Before updating that report list
I'm still worried that these have slowed down on my branch only
@certik Any such incidents before?
@bluescarni Let me know if we can improve this, as of now it is good enough
Sumith Kulal
@Sumith1896
Jun 19 2015 14:42
This message was deleted
I think we need to start designing Polynomial class. @certik
This message was deleted
Francesco Biscani
@bluescarni
Jun 19 2015 14:43
@Sumith1896 to me it looks pretty good at the moment, and the code is still quite simple
my hunch is that to catch up completely with Piranha more tricks will be needed, but these will mess up the code quite a bit and I am not sure you want that right now
Sumith Kulal
@Sumith1896
Jun 19 2015 14:48
Our plan at this stage was to get the low level as much close to Piranha as possible, this is great.
Shivam Vats
@shivamvats
Jun 19 2015 18:53
@bluescarni Hi! We plan to use the polynomial module for series expansions. But I am not sure how to handle series with a constant term. Could you explain how piranha expands series like sin(a + x) wrt x? Is there a symbolic ring?