<peepsalot>
so first 3 points define a plane, and test is which side of the plane the 4th point lies on, or if its coplanar
<InPhase>
Oh good, docs. Because that comment is complete nonsense...
<InPhase>
Like they just threw math words together.
<InPhase>
"takes three points of one hemisphere and returns the orientation of $p_3$ with respect to the halfcircle through $p_1$ and $p_2$. We map this to the 3d orientation predicate of the origin, $p_1$, $p_2$, and $p_3$"
<InPhase>
This does not have that thing we like to call "meaning".
<InPhase>
Three points do not uniquely define a hemisphere, and two points do not uniquely define a halfcircle.
<ndnihil>
and I'm totally not going to grab that torrent I for sure didn't see it on
<InPhase>
The publisher asked me to review it and provide a quote months ago, but I was caught up in some chaos at the time and never even finished reading through the email.
<InPhase>
Guess it's too late now! :)
<InPhase>
I hope it sells some copies. Amazon has it at #167 in 3D Printing Books, where #60 is "So... You Want to 3D Print Food?"
<InPhase>
#65 is "Python for 3D Printing" which uses Python to create OpenSCAD code.
<ndnihil>
hrm
<ndnihil>
time to manipulate the algorithm
<ndnihil>
not sure if it's still as such, but it used to be that you could add/remove an item from your cart over and over to bump its ranking
<ndnihil>
their algo only counted the adds
<InPhase>
peepsalot: So gmp is using bigints... How often do you think it reallocates on a *= or a += / -=?
<InPhase>
peepsalot: So gmp is using bigints... How often do you think it reallocates on a *= or a += or -=? (not division)
<InPhase>
peepsalot: The current algorithm in use uses 9 multiplications and 14 additions or subtractions, with 23 temporary rationals created. However, the same result can be obtained with 9 multiplications, 5 additions and subtractions, 6 assignments, and 3 objects created. I derived it and wrote it out, with fairly reasonable confidence in its correctness.
<peepsalot>
the result of multiplication has bitlength of the sum of its operands. addition has at most one additional bit
<peepsalot>
i don't think it reallocates on shrinking sizes
<InPhase>
Does assignment reuse the existing allocation?
aiyion has quit [Remote host closed the connection]
<InPhase>
peepsalot: That's for a replacement for spherical_orientation. The result of t1 needs to be passed through their "sign()" function that returns a special CGAL sign type, that I assume is just 1, 0, -1.
<peepsalot>
nice, do you know how to fit that into CGAL's twisty maze of templates though?
<InPhase>
They start off very wasteful doing calculations on a point that's all 0, and going through a full determinant. There's no need for all that if you just need direction, which is how I got less ops to start with. Then I just wrote it out with in-place ops.
<InPhase>
I think it's spelled out in the call chain.
<InPhase>
auto newp1 = (typename R::Point_3)p1 gives a type with newp1.x() being x. But I think you can directly call p1.hx(), as that's done below.
<InPhase>
I don't know if p1.x() is a simple reference or a generated type, but either way it can be optimally grabbed with const auto& p1x = p1.hx();
<InPhase>
I think the logical thing is probably to blindly test this. :)
<InPhase>
So... Now how do I convince the OpenSCAD build to take my local cgal source tree...
<InPhase>
I can't just go removing that find_package of CGAL. This does a lot of stuff.
<peepsalot>
i've just been editing /usr/include/CGAL files in place with sudo
<InPhase>
Well that's not great. :)
<InPhase>
Ideally I want to be able to compile two versions with two different source trees side-by-side.
<peepsalot>
i think you can set env CGAL_DIR ?
<peepsalot>
so far i've written some changes to Gmpq_type.h, so that the += -= etc don't rely on local temp and swap
<InPhase>
Wait, they did it that way?
<InPhase>
Usually you build + on top of +=
<InPhase>
It looks like CGAL_ROOT is the critical directory, but you can't set it without rewriting the .cmake files.
<InPhase>
I think they needed a CACHE entry in there to make it user overridable.
<peepsalot>
you could also try setting OPENSCAD_LIBRARIES
<peepsalot>
as seen in CMakeLists.txt and setenv-unibuilds.sh
arebil has joined #openscad
<InPhase>
peepsalot: Ok. It's getting late and I didn't sleep well last night, so my efficacy is dwindling. Here's my best guess of a correct faster implementation of spherical_orientation: https://bpa.st/ESNA
<InPhase>
Obviously if we ever wanted to try to convince them to support this we'd need to make it a template mess like their code. But I think that would compile as is.
<InPhase>
Possibly they wouldn't accept it anyway because it doesn't look mathy anymore, but I'd guess it's at least a bit faster if everything understood so far is true.
<InPhase>
I'm going to put my betting pool numbers at... 11% faster overall runtime.
<peepsalot>
cool i'll see if I can give it a test. still trying to work out how to build from their git repo right now
<InPhase>
Header only. What's to build?
<InPhase>
Although I admit to confusion... the repo is not structured anything like the /usr/include/CGAL/ So I guess you have to ... build the header only library to use it.
<InPhase>
Good luck. :)
<InPhase>
Let me know how that's done.
arebil has quit [Quit: My keyboard has gone to sleep. ZZZzzz…]
<peepsalot>
yeah the paths are all mixed around. i'm just gonna keep editing my /usr/include for now :P
ferdna has quit [Quit: Leaving]
ur5us has quit [Ping timeout: 260 seconds]
arebil has joined #openscad
TheAssassin has quit [Remote host closed the connection]
TheAssassin has joined #openscad
arebil has quit [Quit: My keyboard has gone to sleep. ZZZzzz…]
<peepsalot>
i'm not sure if the cast to R::Point_3 is significant extra load (i probably should have at least cached Point_3 versions of p1,p2,p3) but I couldn't compile without forcing to Point_3 first
<peepsalot>
i still have a hard time following how all these templates connect together
milkandtang has quit [Ping timeout: 268 seconds]
_whitelogger has quit [Ping timeout: 268 seconds]
pie_ has quit [Ping timeout: 260 seconds]
Ekho has quit [Ping timeout: 260 seconds]
_whitelogger_ has joined #openscad
gbruno has quit [*.net *.split]
LordOfBikes has quit [*.net *.split]
rogeliodh has quit [*.net *.split]
luissen has quit [*.net *.split]
InPhase has quit [*.net *.split]
oldlaptop has quit [*.net *.split]
sauce has quit [*.net *.split]
qeed has quit [*.net *.split]
TheCoffeMaker has quit [*.net *.split]
othx has quit [*.net *.split]
sinned6915 has quit [*.net *.split]
ali1234 has quit [*.net *.split]
josephl has quit [*.net *.split]
Fleck has quit [*.net *.split]
L29Ah has quit [*.net *.split]
Polsaker has quit [*.net *.split]
lostapathy has quit [*.net *.split]
ziggurat_ has quit [*.net *.split]
noonien has quit [*.net *.split]
wed has quit [*.net *.split]
juri_ has quit [*.net *.split]
rvt_ has quit [*.net *.split]
fling has quit [*.net *.split]
linext_ has quit [*.net *.split]
peepsalot has quit [*.net *.split]
Xeha has quit [*.net *.split]
Scopeuk has quit [*.net *.split]
Azelphur has quit [*.net *.split]
little_blossom has quit [*.net *.split]
ChanServ has quit [*.net *.split]
t-paul[m] has quit [*.net *.split]
Cadair has quit [*.net *.split]
ali1234[m] has quit [*.net *.split]
drew has quit [*.net *.split]
berndj has quit [*.net *.split]
Teslamax has quit [*.net *.split]
ubitux has quit [*.net *.split]
JakeSays has quit [*.net *.split]
muesli has quit [*.net *.split]
pa has quit [*.net *.split]
arebil has quit [*.net *.split]
clemens3 has quit [*.net *.split]
stefanct has quit [*.net *.split]
buZz has quit [*.net *.split]
milkandtang has quit [*.net *.split]
dalias has quit [*.net *.split]
zingos has quit [*.net *.split]
markasoftware_ has quit [*.net *.split]
_whitelogger has quit [*.net *.split]
RichardP_ has quit [*.net *.split]
ToAruShiroiNeko has quit [*.net *.split]
cbmuser has quit [*.net *.split]
lf94 has quit [*.net *.split]
castawayc has quit [*.net *.split]
la1yv_a has quit [*.net *.split]
Alexer has quit [*.net *.split]
rawgreaze has quit [*.net *.split]
RoyK has quit [*.net *.split]
EkpyroticFrood has quit [*.net *.split]
siege has quit [*.net *.split]
redlizard_ has quit [*.net *.split]
castaway has quit [*.net *.split]
ABSHK has quit [*.net *.split]
raboof has quit [*.net *.split]
jonasbits has quit [*.net *.split]
crazy_imp has quit [*.net *.split]
ndnihil has quit [*.net *.split]
TheAssassin has quit [*.net *.split]
aiyion has quit [*.net *.split]
teepee has quit [*.net *.split]
snaked has quit [*.net *.split]
NoGare[m] has quit [*.net *.split]
whileone[m] has quit [*.net *.split]
Zauberfisch has quit [*.net *.split]
knielsen has quit [*.net *.split]
kanzure has quit [*.net *.split]
niyawe has quit [*.net *.split]
SamantazFox has quit [*.net *.split]
t4nk_freenode has quit [*.net *.split]
hyperair has quit [*.net *.split]
ccox has quit [*.net *.split]
_whitelogger has joined #openscad
Taneb0 is now known as Taneb
ziggurat_ has quit [*.net *.split]
noonien has quit [*.net *.split]
wed has quit [*.net *.split]
juri_ has quit [*.net *.split]
rvt_ has quit [*.net *.split]
fling has quit [*.net *.split]
linext_ has quit [*.net *.split]
peepsalot has quit [*.net *.split]
Xeha has quit [*.net *.split]
Scopeuk has quit [*.net *.split]
stefanct has quit [*.net *.split]
Azelphur has quit [*.net *.split]
little_blossom has quit [*.net *.split]
ChanServ has quit [*.net *.split]
t-paul[m] has quit [*.net *.split]
Cadair has quit [*.net *.split]
ali1234[m] has quit [*.net *.split]
drew has quit [*.net *.split]
berndj has quit [*.net *.split]
Teslamax has quit [*.net *.split]
ubitux has quit [*.net *.split]
JakeSays has quit [*.net *.split]
muesli has quit [*.net *.split]
pa has quit [*.net *.split]
arebil has quit [*.net *.split]
clemens3 has quit [*.net *.split]
buZz has quit [*.net *.split]
RichardP_ has quit [*.net *.split]
ToAruShiroiNeko has quit [*.net *.split]
cbmuser has quit [*.net *.split]
lf94 has quit [*.net *.split]
splud has quit [*.net *.split]
castawayc has quit [*.net *.split]
Alexer has quit [*.net *.split]
rawgreaze has quit [*.net *.split]
RoyK has quit [*.net *.split]
EkpyroticFrood has quit [*.net *.split]
la1yv_a has quit [*.net *.split]
ABSHK has quit [*.net *.split]
siege has quit [*.net *.split]
castaway has quit [*.net *.split]
redlizard_ has quit [*.net *.split]
raboof has quit [*.net *.split]
crazy_imp has quit [*.net *.split]
jonasbits has quit [*.net *.split]
ndnihil has quit [*.net *.split]
rogeliodh has quit [*.net *.split]
gbruno has quit [*.net *.split]
hisacro_ has quit [*.net *.split]
zingos has quit [*.net *.split]
markasoftware has quit [*.net *.split]
LordOfBikes has quit [*.net *.split]
ur5us has quit [*.net *.split]
InPhase has quit [*.net *.split]
luissen has quit [*.net *.split]
oldlaptop has quit [*.net *.split]
sauce has quit [*.net *.split]
TheCoffeMaker has quit [*.net *.split]
dalias has quit [*.net *.split]
qeed has quit [*.net *.split]
ali1234 has quit [*.net *.split]
othx has quit [*.net *.split]
sinned6915 has quit [*.net *.split]
josephl has quit [*.net *.split]
Fleck has quit [*.net *.split]
L29Ah has quit [*.net *.split]
Polsaker has quit [*.net *.split]
lostapathy has quit [*.net *.split]
teepee has quit [*.net *.split]
TheAssassin has quit [*.net *.split]
aiyion has quit [*.net *.split]
pie__ has quit [*.net *.split]
Taneb has quit [*.net *.split]
ndimitrij has quit [*.net *.split]
Ekho has quit [*.net *.split]
fardog has quit [*.net *.split]
snaked has quit [*.net *.split]
NoGare[m] has quit [*.net *.split]
whileone[m] has quit [*.net *.split]
knielsen has quit [*.net *.split]
Zauberfisch has quit [*.net *.split]
kanzure has quit [*.net *.split]
niyawe has quit [*.net *.split]
SamantazFox has quit [*.net *.split]
t4nk_freenode has quit [*.net *.split]
ccox has quit [*.net *.split]
hyperair has quit [*.net *.split]
ToAruShiroiNeko has joined #openscad
othx has joined #openscad
<teepee>
quite a difference for a small change, but I guess that makes sense as the geometry processing is just the same calculations over and over again
lastrodamo has joined #openscad
whileone[m] has joined #openscad
dTal has joined #openscad
<cbmuser>
knielsen: sorry, I fell asleep yesterday, at it now
mhroncok has joined #openscad
<Scopeuk>
I suppose it's optimisation done properly, identify where you spend your time and then focs on the bits that are called frequently and expensive
<Scopeuk>
s/focs/focus
<Scopeuk>
sometimes it really pays off
whileone[m] has quit [Quit: Bridge terminating on SIGTERM]
ali1234[m] has joined #openscad
timiimit has joined #openscad
timiimit has left #openscad [#openscad]
t-paul[m] has joined #openscad
Cadair has joined #openscad
NoGare[m] has joined #openscad
whileone[m] has joined #openscad
Xeha has joined #openscad
arebil has joined #openscad
<InPhase>
peepsalot: Nice. :)
<InPhase>
peepsalot: So basically it made that routine 3 times faster then?
<InPhase>
Is the 21% overall speed-up with optimization enabled?
<InPhase>
Also... Perhaps most importantly... Did it actually work and still pass the tests? It's one thing to prove a thing "should" work, and another to try it.
Xeha has quit [Ping timeout: 252 seconds]
Xeha has joined #openscad
<InPhase>
peepsalot: Oh, yeah. Reviewing the final version I see I also foolishly made the types I was modifying const. :) If this passes all tests and it seems worth trying to submit it, we should try caching the points first as you said, and convert all the autos to the right templated types. And also some sort of comment showing the equation is definitely warranted, probably looking something like the
<InPhase>
derivation notes in my bpa.st above (including noting that it's the dot of p3 with the cross-product of p1 and p2), as it's really hard to see the equation in that optimized form.
<InPhase>
There will be someone resisting it as a submission, so it will be important to note both the more efficient form of that equation, AND the benchmarking results and how often this gets called while crunching results, to raise the justification for the ugliness. A solid case needs to be constructed for the positive impact when doing something this unfriendly to human eyes.
<InPhase>
The theoretical case for bypassing all the allocations and how this impacts runtime will also need to be spelled out.
<InPhase>
It's not just the allocation overhead, but also cache locality that arises here.
TheAssassin has joined #openscad
arebil has quit [Quit: My keyboard has gone to sleep. ZZZzzz…]
<peepsalot>
InPhase: yeah 21% with optimization enabled, specifically on example024.scad
<peepsalot>
all of OUR tests passed. i haven't yet tried CGAL's test suite
<peepsalot>
since our general test suite isn't very heavy on CGAL Nef ops, there wasn't nearly as much speedup on our overall tests
<peepsalot>
"time ctest" after: real 4m57.376s, user 4m11.511s, sys 1m3.932s
<peepsalot>
"time ctest" before: real 4m59.810s, user 4m16.050s, sys 1m4.975s
arebil has joined #openscad
<InPhase>
Yeah, I guess we need some more heavy CGAL stuff in the testing suite for this sort of overall benchmarking
<peepsalot>
however my cgal-specific test run, including Heavy, was 5.8% faster user time overall
<peepsalot>
"time ctest -C All -R cgal" before: real 4m57.416s, user 4m43.125s, sys 0m22.492s
<peepsalot>
"time ctest -C All -R cgal" after: real 4m41.313s, user 4m26.728s, sys 0m21.781s
<InPhase>
5.8% avg on CGAL stuff and 21% on the CGAL-op-heavy stuff is not bad at all for a change to just one function.
<peepsalot>
tbf, i changed a lot of Gmpq's member functions too
<InPhase>
Ah. Did you try separately to see if both are worth upstream submission?
<peepsalot>
i was testing out my changes alone before adding your sphere_orientation optimization. it was slightly faster than stock but I didn't write down performance numbers for that
<InPhase>
It's possible they are synergistic if you were modifying the +=, -+, and *= ops.
<InPhase>
The thesis behind switching to those was to avoid the temporary allocation. :)
<InPhase>
If this is true, then we would need both to be accepted.
<InPhase>
Oh, gmpq is a CGAL specific modification of gmp?
<InPhase>
Then I guess it's all one pile.
<peepsalot>
yeah its a layer on top of GMP's C interface. GMP also has mpq_class and mpz_class which are its own C++ layer, and CGAL provides some kernel adapting functions for that too
<peepsalot>
InPhase: did you see my modifications to Gmpq_type.h and Gmpz_type.h in that commit i linked? would appreciate a code review on those too when you have a moment
<InPhase>
I didn't scroll that far down.
<InPhase>
Looks like a list. I just messaged myself the link so I remember to review that later today.
arebil has quit [Quit: My keyboard has gone to sleep. ZZZzzz…]
<peepsalot>
mpq_t is basically two mpz_t, one for numerator and denominator. you can operate on each component individually with mpz_* functions, but your are required to use mpq_canonicalize (removes common factors) on the results
<peepsalot>
one thing i'm not sure about, is how Gmpq calls mpq_canonicalize when multiplying or dividing Gmpq with a Gmpz, but not when adding and subtracting
<peepsalot>
Guest63: if you mean units, there are none. but most people design in mm, as that's a common unit for 3D printer slicers when working with STL
<Guest63>
So assume the numbers on the axes are in mm?
<peepsalot>
sure
<peepsalot>
InPhase: still 23GB of memory bandwidth which might be further optimizable though
ran has joined #openscad
<InPhase>
peepsalot: Wow, that was a massive change in total allocations.
<InPhase>
25% reduction.
<InPhase>
I usually don't profile code, because I design intentionally for sensible allocation and know pretty well what my own code is going to do. But you really highlighted a good use of profiling there for a massive underperformant codebase that gets dropped in your lap.
<InPhase>
We would have never spotted that by hunting and pecking.
<InPhase>
Well, I should say I usually don't profile large code. I all the time profile components.
<InPhase>
And then I know what they're going to do. :)