Lessons from my port of JSCAD to C Sharp.

[briansturgill]

Over the last month and a half I ported 28,000 lines JSCAD Javascript to C# (26,000 from modeling, 2,000 from io).
To put it in perspective, JSCAD modeling is 35,000 lines in total. Oddly, C# seems slightly less verbose than JS... I didn't expect that.

First of all, let me say I'm very impressed with the code base. Yes, as in any large project, some code is better than others, but I only found 2 (sets) of bugs during the porting process. Lots of unit test greatly helped!

Running benchmarks, I'm very impressed with the speed you've manage to get from JavaScript. I'll have more firm results later, but initially it looks like C# is about 1/3 faster for code that is a straight translation from JavaScript. When I've rewritten portions the C# way, it runs at about 2x faster. I've been benchmarking some special C# classes (System.Numerics) that use Intel/ARM SIMD instructions. At least for standard Vec3/Mat4 Transforms, it runs 6x faster than my Vec3/Mat4 code I translated to C#. Overall I'm guessing I'll be able to achieve overall a 2x to 3x speed up, but will have the drawback of needing to switch to single precision floating point.

While many times your code base stretched beyond my JavaScript knowledge, I've found a few cases where there
seems to be confusion. Some of these are specifically failure to use modern JS, and I'll bug report them.

But one very confusing thing to me to is the use of index vectors in some of the algorithms (Graham hull scan and earcut and maybe one other.) The purpose of the parallel use of the index vector in earlier times was it saved data movement from the much larger floating point numbers. That made sense when you were using 16 bit ints routinely... but is crazy in JavaScript. Your "ints" are floating point doubles. Further, due to the way you structure your data (vec2, vec3), you are not every really moving 2 or 3 doubles, but rather a pointer containing those doubles. The use of the index vector is just greatly increasing memory usage, causes unecessary indirection arithmetic, additional data allocation/deallocation and generally messes with your CPU cache performance. It's just a bad idea.

Here's my rewrite from scratch of the Graham scan (convex hull) algorithm. It is a replacement for hullGeom2.js/hullPoints2.js. It gets rid of the index vector and the use of Atan2 and is generally easier to understand... translation back to JS should be straight forward.

namespace CSharpCAD;

public static partial class CSCAD
{
    private class pt
    {
        internal readonly Vec2 point;
        internal readonly float_t angle;
        internal readonly float_t distSq;
        internal pt(Vec2 point, float_t angle, float_t distSq)
        {
            this.point = point;
            this.angle = angle;
            this.distSq = distSq;
        }
    };
    /*
     * Create a convex hull of the given geom2 geometries.
     * Uses https://en.wikipedia.org/wiki/Graham_scan
     */
    public static Geom2 HullGeom2(params Geometry[] geometries)
    {
        // Extract unique points from the geometries.
        // To avoid a second pass, also determine the minimum point.
        var uniquePoints = new HashSet<Vec2>();
        var min = new Vec2(float_t.PositiveInfinity, float_t.PositiveInfinity);
        foreach (var g in geometries)
        {
            var sides = ((Geom2)g).ToSides();
            foreach (var side in sides)
            {
                var point = side.v0;
                uniquePoints.Add(point);
                if (point.y < min.y || (point.y == min.y && point.x < min.x))
                {
                    min = point;
                }
            }
        }

        // Returned "angle" is really 1/tan (inverse of slope) made negative to increase with angle.
        // This function is strictly for sorting in this algorithm.
        float_t fakeAtan2(float_t y, float_t x)
        {
            // The "if" is a special case for when the minimum vector found in loop above is present.
            // We need to insure that it sorts as the minimum point. Otherwise this becomes NaN.
            if (y == 0 && x == 0) { return float_t.NegativeInfinity; }
            return -(x / y);
        }

        // Gather information for sorting by polar coordinates.
        var points = new List<pt>(uniquePoints.Count);
        foreach (var v in uniquePoints)
        {
            // Use of fakeAtan2 avoids use of Math.Atan2 which slows things down.
            // A simple timing test suggests it saves about 10% of total time.
            var angle = fakeAtan2((v.y - min.y), (v.x - min.x));
            //var angle = Math.Atan2((v.y - min.y), (v.x - min.x));
            var distSq = min.SquaredDistance(v);
            points.Add(new pt(v, angle, distSq));
        }
        points.Sort((pt pt1, pt pt2) => pt1.angle < pt2.angle ? -1 : pt1.angle > pt2.angle ? 1 :
            pt1.distSq < pt2.distSq ? -1 : pt1.distSq > pt2.distSq ? 1 : 0);

        // ccw returns:  < 0 clockwise, 0 colinear, > 0 counter-clockwise.
        float_t ccw(Vec2 v1, Vec2 v2, Vec2 v3) => (v2.x - v1.x) * (v3.y - v1.y) - (v2.y - v1.y) * (v3.x - v1.x);
        var stack = new List<Vec2>(); // Start with empty stack
        foreach (var point in points)
        {
            var cnt = stack.Count;
            while (cnt > 1 && ccw(stack[cnt - 2], stack[cnt - 1], point.point) <= C.EPSILON)
            {
                stack.RemoveAt(stack.Count - 1); // Pop - gets rid of colinear and interior (clockwise) points.
                cnt = stack.Count;
            }
            stack.Add(point.point); // Push
        }

        if (stack.Count < 3) return new Geom2();

        return new Geom2(stack);
    }
}

[hrgdavor]

wow, that is a massive undertaking. looking forward to seing performance comaprisons. Maybe there will be lessons there to point to some perf improvements of jscad JS code.

[briansturgill]

wow, that is a massive undertaking. looking forward to seing performance comaprisons. Maybe there will be lessons there to point to some perf improvements of jscad JS code.

The hull code above is an example. It eliminates a 2 data passes and a data copy that was done in JS. And has a more efficient way of doing a polar coordinate sort.

[briansturgill]

Oh, forgot to add, it also removed the index array, which would eliminate another data pass/data copy, and of course all of the silly indirections.

[z3dev]

@briansturgill thanks for the new implementation. We will try to port to javascript.

just one request, please create new issues for anything that you fix or reimplement. That will make it easier to discuss in detail, and keep this discussion a little more readable.

[hrgdavor]

Also make sure to warmup JS engine, as I have seen jscad operations can go 2-4x faster when run subsequently.

[briansturgill]

When I was timing hull() I ran 10,000 hulls and did it more than once.
Generally I never believe only one run.

[hrgdavor]

That is excellent @briansturgill ....

@platypii would you be interested in converting this to JS, and maybe do some perf tests, this looks very promising :)

[z3dev]

@briansturgill any chance of playing with the C# version? I don’t see the repository anywhere.

[briansturgill]

I am about 2 weeks from a public release.
At the moment I'm fixing documentation, and finalizing the C# API which, for various reasons, differs from the JS one.
If you really need access before then I could drop a .zip archive somewhere? But I don't want to put it on Github yet.
BTW, I've MIT licensed my translation, so it will be freely available.

[z3dev]

@briansturgill no problem. i'll take the new car out for a spin once the new paint is dry. it has to look good as well as run like the wind. :)

[hrgdavor]

@briansturgill you may also be interested in #1063

[briansturgill]

I look forward to seeing it. While my primary goal is an OpenJSCAD replacement as a desktop version, the UI will all be JS and done like an electron App, but with C# replacing Node. However, my secondary goal was both a server side and a client side web app... the client side being WebAssembly, translated from C#. It is easy to do all three from the same code base.
If Walnut proves significantly faster, then of course I'll eventually consider swapping out that portion.

Oh, on a related note, I tried moving the code base to single precision to take advantage of a Microsoft implementation of Vectors, Mat4, etc. that had SIMD instruction speed ups. Alas, that failed. I did however discover an number of problems in the JSCAD code base in attempting this. Feed back from that (along with fairly easy to make changes) should appear in a couple of weeks.

[hrgdavor]

Cool, I love the fact that you effort also has potential to improve jscad. I am curious to see performance comparisons, and then it would be interesting what could be done in jscad to improve the speed too.