# Difference between revisions of "User:NyahCh3ck20/GSoc2013/Coding Report"

NyahCh3ck20 (talk | contribs) (→22 July - 28 July) |
NyahCh3ck20 (talk | contribs) (→22 July - 28 July) |
||

Line 250: | Line 250: | ||

New_determinant Test: | New_determinant Test: | ||

− | Det: -3291.00 | + | Det: -3291.00 |

− | real 0m54.921s | + | real 0m54.921s |

− | user 0m54.815s | + | user 0m54.815s |

− | sys 0m0.054s | + | sys 0m0.054s |

+ | |||

+ | Also, another further test reveals: | ||

+ | Summary: | ||

+ | |||

+ | bn_mat_determinant() | ||

+ | |||

+ | GCC 4.6.3 compiles both existing libbn and my implementations to roughly equally efficient binary on x86-64 if optimizations are enabled. Without compiler optimizations, mine is clearly faster. | ||

+ | |||

+ | Without optimizations, mine runs in 154 cycles (minimum and median), whereas the libbn one takes 210 cycles minimum, 219 cycles median. (Mine is almost a third faster!) | ||

+ | |||

+ | With typical optimizations, '-O2', mine runs in 92 or 93 cycles (minimum and median), whereas the libbn one runs in 95 cycles (minimum and median). | ||

+ | |||

+ | The relative difference in the results for a large set of random matrices was always under one billionth, 10-9. That is, the error is roughly the same order as the precision of a square root of some value, sqrt(). | ||

+ | |||

+ | bn_mat_inverse() | ||

+ | |||

+ | Using GCC-4.6.3, my implementation is demonstrably faster than the existing libbn implementation -- even if the existing libbn implementation cannot invert all non-singular real-valued 4x4 matrices! (I verified some of my random matrices using Maple.) | ||

+ | |||

+ | Without optimization, my implementation is three times as fast, completing in 544 cycles (median value), whereas libbn implementation requires 1660 cycles (median value). | ||

+ | |||

+ | With -O2, my implementation takes 423 (minimum) to 432 (median) cycles, whereas libbn implementation takes 610 (minimum) to 660 (median) cycles. | ||

+ | |||

+ | My preferred maximum level of optimization is '-O3 -fomit-frame-pointer'; my implementation takes 423 (minimum) to 427 (median) cycles, whereas libbn implementation takes 466 (minimum) to 483 (median) cycles; in the median case, my implementation is still 11% faster. | ||

+ | |||

+ | The maximum level of optimization I tried is '-O3 -fomit-frame-pointer -ftree-vectorize -march=native -mtune=native'. Mine still runs in 420 to 426 cycles, whereas libbn took 480 to 500 cycles. | ||

## Revision as of 13:36, 25 July 2013

## Contents

#### Coding Log Report for GSoc 2013

Daily log:

## 17 June - 23 June

Coding Begins for GsoC working on codepatch to be uploaded to brlcad uploaded the sourcefile for new push routine which supports the -x option for xpush but still needs further testing and modifications.

18 june 2013 Added a new functionality to new push routine where the push would recognise the the xpush case even in a case where the -x option is ommitted or ignored.

Tested the new routine and extracted patch to be uploaded to sourceforge replacing the previous push file I uploaded.

To discuss with mentors whether there is an implementation of the Inverse of a 4x4 matrix in the brlcad source code.

Looking at the implementations of the Inverse of the matrix in BRL-CAD

## 24 June - 30 June

- Monday June 24

Looked at the definitions for the inverse of a 4x4 matrix as defined in /src/libbn/mat.c. However, i realised orthogonal matrices were not taken into consideration. So added functionality to determine inverse faster for othogonal matrices and to upload patch to sourceforge shortly.

Started creating structures for the pull routine that is ( pull_obj and p_solid) structures to hold objects to be pushed and solids currently being pushed on a CSG tree. Code to be added to sourceforge Shortly.

re-read the HACKING file to make sure i conformed with the coding standards for BRL-CAD.

- Tuesday June 25

Further tested the bn_mat_inverse routine(src/libbn/mat.c) and modified patch that was to be uploaded yesterday but failed due to poor network connection.

Looked at the libbn library especially mat.c which would be useful for implementing the pull.

Studied the vmath.h header and discovered the transform.c file which could be applied in creating the pull routine.

Uploaded the pull.c first patch and bn_mat_inverse patches due to failure in network for them to be uploaded yesterday. Inverse Matrix support for orthogonal matrices

Will need some clarification from mentors concerning my design strategy for the pull routine.( The necessary functions i would need to create or call from the source) in order to implement a complete pull routine.(Asked on mailing list.) still to continue work on push and xpush merger.

Saw the importance of magic numbers in taking note of visited nodes along the CSG tree. Also, thought of checking the matrix transformations for each node to determine if node has been visited but since magic IDs were used in the push then i could use both in pull when performing the inorder walk from the leaf(solid) nodes.

Moreover, for objects in database, dp->d_uses was used but not safe as defined push.

- Wednesday July 26

Earlier part of the day used for preparation for and wrote an Information System test before working.

Added the new pull routine to the setup.c(/src/mged/setup.c) interface and included the new command into the CMakeLists.txt file(/src/libged/CMakeLists.txt) in the brlcad source

These patches also included the removal of the xpush command to support the new push and xpush. Patches to be uploaded to sf.

Added new pull routine declaration(ged_pull(struct ged *,int, char *[])) to the ged.h header so it can be accessed by other files. patches to be uploaded to sf.

Added new pull to tclcad_obj.c file(/src/libtclcad/) although with support of more than one arguments i'll first of all try to test with only one argument then see how far it goes;this is so that it's available in the internal database interface.

Added tentative ged_pull() function definition to the pull.c file to enable it to be accessed by files calling function.

However since ged_pull() routine does not compile code can't compile due to unused variables so will create some dummy operations just to see how blank routine works and get it started.

Well just realised that the orthogonal matrix consideration in the bn_mat_inverse routine in mat.c is causing the benchmark tests to fail. Gotta sit on it and fix the bug. Pull Patch

- Thursday 27 June

Travelled to Douala and spent the whole day trying to cash the prepaid GSoC deposit. However, tried working on a bug in the mat.c file(/src/libbn) where the inserted code patch for orthogonal matrix support is giving wrong answers during the benchmark test. Discovered a little error calling the bn_mat_mul2() routine and now code passes 3 benchmark tests and fails 3.Will perfect code and upload codepatch tomorrow on sf.

- Friday 28 June

Looking at the bn_mat_inv() routine and performing some tests to ensure all benchmark tests succeed.

Checked the orthogonal matrix support and code still fails 3 regression tests after testing and checking need some assistance for this. Started a detail analysis and study of the push command from the ged_push() routine. This is to enable me understand perfectly the implementation hacks of the push in order to implement a push correctly especially when it comes to dealing with the points and matrix transformations at the node and leaf levels on the CSG tree.

To check all reviews from code patches so as to start working on them tomorrow. Modified push Modified bn_mat_invThis patches passes some regression tests; but i don't understand why it still doesn't work perfect. Don't really see the problem here

## 1 July - 7 July

- Monday 1 July

Well did not code because of Preparations to attend the Google Student's Ambassador's Summit in Nairobi, Kenya for Africa. This summit goes on for the whole week. But will try to fix problems with my code patches while at the summit.

- Tuesday 2 July 2013

Boarded Kenyan Airways flight from Douala Int'l to the Jomo Kenyatta Int'l in Nairobi which took about 5 hours; then registered with the GSA team.

- Wednesday 3 July 2013

Attended the First day of Summit where we had talks with Google Engineers about being a good ambassador. Presentations were given by Mr. Obum Ekeke , Tayib Fall and others about opportunities at Google.

- Thursday 4 July 2013

Second Day of Summit focused on Google products like Adwords, Adsense and other products; also, Engr. Giacomo(Googler) gave a presentation on Webmaster tools and Google Search in general.

- Friday 5 July 2013

Third day of Summit where we focused on making greater impacts on our communities in Africa; with awards given to Star GSAs of the previous years. Shared ideas and experiences for the Moonshot idea competition organised as per country we emerged 3rd after South Africa and Kenya. Developed plans to execute our moonshot idea as we returned home after the summit

- Saturday 6 July

Preparing for return trip to Douala Int'l and went round Nairobi for shopping and other stuffs.

- Sunday 7 July

Returned from Nairobi to Douala and after meeting family travelled to Buea to prepare for coming week.

## 8 July - 14 July

- 8 July 2013

Wrote a report to be submitted to the Vice Chancellor concerning my experiences on Google Student Ambassador's summit and preparing for a Numerical Analysis Exam Took further look at source code(/src/push.c) to see how the matrix transformations are applied to the coordinate points of the node so as to determine a way of extracting the original matrix transformation or almost exact matrix transformation for source code.

Glad the Dean of the faculty of Science authorized the installation of Internet in the CS so we can have 24/7 Internet access

- Tuesday 9 July

Wrote my Numerical Analysis exams and to finish with exams tomorrow so i can focus on GSoC full time.

- Wednesday 10 July

Finished writing exams today and started preparing previous code patches(mat.c,push.c,pull.c) so that when the Internet access is available all files will be uploaded so as to get commit access.

- 11 July 2013

studied the brlcad primtive internals like(torus, spheroids, toruses (torii), spheres, ellipsoids, pyramids) so as to be able generate the original transformation matrix. Torus, struct rt_tor_internal Centerpoint, point_t v, is obviously the translation. The orientation and scale is defined by vect_t h, and radiuses by fast_t r_h and fast_t r_a. Because of symmetries, the original transformation matrix must have contained a translation of v, and a rotation that brings vect_t h to an axis

Spheres and ellipsoids, struct rt_ell_internal Centerpoint is at point_t v, which again is obviously the translation done.There are three vectors, point_t a, point_t b, and point_t c, that describe the spheroid axes. This means that I can construct the transformation matrix that transforms the unit sphere to this sphere directly.

for Truncated general cones, struct rt_tgc_internal Centerpoint is at vect_t v, with vect_t h describing the axis. The base of the cone is, I think, described by the vectors vect_t a and vect_t b, and the top of the cone by vectors vect_t c and vect_t d. This implies that aÂ·b=0 and cÂ·d=0, but they may not be perpendicular to h, since the base and top of a general cone may be cut along any direction. v is the translation, and h should be along an axis (probably z axis). This yields three vectors (h, f, g), that along with the translation vector v define the transformation matrix just like in the ellipsoid case.

Also, looked at data type for Pyramids: struct rt_arb8_internal This data type contains between four (tetrahedron) to eight vertices as point_t variables. Pyramids and tetrahedra have the apex vertex perpendicular and center to a face. This can be taken as the face vector. The second vector is one that bisects an edge (the longest edge?) of the face perpendicular to the apex. The third vector is their cross product, and is either towards a vertex (a tetrahedron) or halves another edge of the face perpendicular to the apex (a pyramid). These three vectors can be used to regenerate the initial transformation matrix, with e.g. the base on the XY plane, and the apex along the Z axis.

To look at wedges, Boxes, and convex polyhedra tomorrow.

- 12 July 2013

Prepared complete patches and uploaded to sf to replace the existing patches for new push routine(push.c), pull routines(pull.c) and bn_mat_inverse routine(mat.c) with orthogonal matrix support. Since there is no internet connection, I could not create these patches with the current svn checkout.

Continued study of implementation of push.c so as to see what happens to coordinate points of the node, to determine how some form of the original matrix transformation is stored so as to ease restore during the pull routine.

- 13 July 2013

Did no work because of a long meeting( in my capacity as Auditor of Computer Engineering students Association) of over 5 hours with the Dean of Faculty to draft modalities for new student union body and draft constitution and mission to govern association.

Will start implementing the pull leaf function as from Monday which will extract the matrix transformations from the primitives(solid) or leaf nodes.

## 15 July - 21 July

Monday 15 July

- Implemented the pull_leaf routine which build a linked list for object's tree which would be used in extracting matrix transformations in leaf_mat() routine I am to start working on tomorrow.
- continued with the implementation of the ged_pull by adding -d option to command to enable a debug of command as in push -d

Todo: To ask on mailing list how to generate a Magic ID since its needed for the pull.

Tuesday July 16 2013

- Further worked on the pull_leaf routine to make sure list is properly built and created loop to free up list if errors occured during the list build like pulling unpushed nodes.

- Started working on a loop to move through the nodes of the linked list making the necessary mat_t changes while moving upwards modifying the current matrix transformation as it encounters a new leaf when necessary calculating and storing the inverse matrices up the tree till it reaches the root. This will then be followed by writing these changes to the database.

TODO: Ask on mailing list how my current working model solves the method so as to make the necesary changes in approach and continue.

Wednesday July 17, 2013

- Finished writing loop that moves backwards on the newly built list of nodes on the tree, performing inverses as necesary,storing the changes on the node, writing to database and setting the matrix transformations for primitives(leaves) to identity as necessary.

- Wrote loop that frees up built list and returns result of object pull.

- started testing of pull command and to continue fixing bugs. Till command is ok before adding support to pull more than one object.

- Performed another benchmark test for the orthogonal matrix support for bn_mat_inverse() in mat.c

- Uploaded code patches for mat.c and combined push and xpush to sourceforge.

Todo: fix all problems with with currrent and past patches and upload to sf for mentor review.

Thursday July 18, 2013

- Started working on compile time errors of the pull.c by fixing some pointer casts and others.

Friday July 19, 2013

- Finished debugging compile errors and started testing routine.

- Tested for improper use of command(pull 'no object'), returned correct errors

- Tested for pulling a primitive.(returned correct error message).

- Tested for pulling an object which has not been previously pulled.(mged crashed due to segmentation fault) to start working on bug next week.

Will be taking tomorrow off since its my birthday and start working on bugs and patches next week.

## 22 July - 28 July

Monday July 22, 2013

- Added -x option to push.c to support new xpush command(recreated and tested new push command). Spent whole day debugging and still have not succeeded in removing bug causing the

loss of options to push command.

- Created new patch for pull command and patch applies cleanly but command still further development and debugging.

Tuesday July 23, 2013

- Installed Internet in the CS Lab so as to increase efficiency for BRL-CAD.

- Started downloading latest svn checkout for BRL-CAD source

- Set up account on bz.bzflag.bz server and Started downloading tutorials on how to use ssh and GNU Screen

- Upgrading my SL 6.2 distro so as to start further work on patches tomorrow.

Wednesday July 24, 2013

- Enabling pull routine to be able to pull a non leaf node; that is routine is able to pull geometric transformations from any node up to the root.(as @Sean adviced me on mailing list.)

- Found bug in code which returns error when pulling non-leaf node. Started fixing

- Prepared patch to stub pull routine unto brlcad using svn diff(Uploaded to sf Here

- Tests of pull routine shownhere

Thursday July 25, 2013

- Tested new algorithm for bn_mat_inverse() which used only Uses 100 multiplications and 61 additions or substractions.

- Tested new algorithm for bn_mat_determinant which requires only 34 multiplications and 20 additions or substractions, saving 6 multiplications

and 3 additions or substractions compared to the previous one. Integrated code into brlcad and tested. new passed all benchmark tests. Created patch and uploaded to sf

- Wrote Tests to compare runtime of old_determinant against new determinant routine which returned the following:

Old_determinant Test:

Det: -3291.00 real 1m5.151s user 1m5.081s sys 0m0.019s

New_determinant Test:

Det: -3291.00 real 0m54.921s user 0m54.815s sys 0m0.054s

Also, another further test reveals: Summary:

bn_mat_determinant()

GCC 4.6.3 compiles both existing libbn and my implementations to roughly equally efficient binary on x86-64 if optimizations are enabled. Without compiler optimizations, mine is clearly faster.

Without optimizations, mine runs in 154 cycles (minimum and median), whereas the libbn one takes 210 cycles minimum, 219 cycles median. (Mine is almost a third faster!)

With typical optimizations, '-O2', mine runs in 92 or 93 cycles (minimum and median), whereas the libbn one runs in 95 cycles (minimum and median).

The relative difference in the results for a large set of random matrices was always under one billionth, 10-9. That is, the error is roughly the same order as the precision of a square root of some value, sqrt().

bn_mat_inverse()

Using GCC-4.6.3, my implementation is demonstrably faster than the existing libbn implementation -- even if the existing libbn implementation cannot invert all non-singular real-valued 4x4 matrices! (I verified some of my random matrices using Maple.)

Without optimization, my implementation is three times as fast, completing in 544 cycles (median value), whereas libbn implementation requires 1660 cycles (median value).

With -O2, my implementation takes 423 (minimum) to 432 (median) cycles, whereas libbn implementation takes 610 (minimum) to 660 (median) cycles.

My preferred maximum level of optimization is '-O3 -fomit-frame-pointer'; my implementation takes 423 (minimum) to 427 (median) cycles, whereas libbn implementation takes 466 (minimum) to 483 (median) cycles; in the median case, my implementation is still 11% faster.

The maximum level of optimization I tried is '-O3 -fomit-frame-pointer -ftree-vectorize -march=native -mtune=native'. Mine still runs in 420 to 426 cycles, whereas libbn took 480 to 500 cycles.

- Wrote Tests to compare Inverse of Old matrix inverse routine and new_matrix Inverse routine which returned the following results:

Old:

New:

# Original Timeline

Since i'll have to attend the Google Student Ambassador's summit in the first days of July and exams begin on the early part of July i'll move some of the work overhead to june when coding begins.

### Community Bonding Period

May 30

June 13 TODO: combination of push and xpush routine.

changed xpush to push -x

June 14:

Integration into MGED and tests of new command.