Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Flumble
Yes Man
Posts: 2201
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Fri May 03, 2019 3:39 pm UTC

Make some kind of ziplist iterator that provides immutable references to all previous and next items while providing a mutable reference to the current item. :D

Would it make sense to map over the collection producing a collection of Option<Mesh> objects (Some if a mesh is generated) and then zip the two collections? Or can the (re)generation of one mesh depend on the (re)generation of another mesh during the same iteration?

Tub
Posts: 461
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Fri May 03, 2019 10:00 pm UTC

Flumble wrote:Would it make sense to map over the collection producing a collection of Option<Mesh> objects (Some if a mesh is generated) and then zip the two collections? Or can the (re)generation of one mesh depend on the (re)generation of another mesh during the same iteration?

Yeah, I can push all the changes to a separate collection, then merge the changes back into the original collection as a separate pass. That's what I implemented for now. It's cheap compared to the mesh generation, but it's still pointless overhead just to appease the compiler.

I was promised readable idiomatic code with zero-costs abstractions, and now I need to sacrifice both readability and performance just to make it compile. Not sure how I feel about that.

Next step is to implement the actual Octree in Rust. Let's see how pretty the solution for a recursive data structure ends up. I'm anticipating more pain because each object must be both in a HashMap (based on id) and in the Octree (based on location), and although I can guarantee that to be safe, I'm afraid the compiler won't believe me unless I accept the overhead of ref-counting smart pointers.

Tub
Posts: 461
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Sat May 04, 2019 9:00 pm UTC

Update: I ended up solving the mutability problem by using std::Cell. Cells cheat the whole lifetime issue by disallowing getting a reference to the things inside. You can just copy values in, or copy the current value out. With those semantics, it's safe for them to allow changing the value inside without having a mutable reference to them! Now I can do the whole iteration and regeneration on immutable objects, but still clear the dirty-bit inside a Cell<bool>. Won't solve all of my problems, but for this specific problem the borrow checker is happy.

Octree went well. I needed a bit more boilerplate to specify the type of child pointers (either nullptr, pointing to another node, or pointing to a leaf with objects), but thanks to enums that was a lot less code than other statically typed languages would have required.
For now the octree leaves just store the object ids instead of references to the objects, neatly avoiding all the borrowing issues. That's another HashMap lookup per visible object per frame, but those lookups are cheaper than drawing the object, so I guess it's fine. Still irks me, but it's fine.

The previous javascript implementation used a Heap, added all the visible objects by distance, then continued to draw them front-to-back. In rust, I ended up implementing this as a lazy iterator, allowing me to consume items before the Heap is completely filled. Not sure if that's actually faster, but it was a fun challenge.
The Iterator required a ton of boilerplate for all the types, their trait implementations and everything (the BinaryHeap requires 4 traits on its entries just to specify sort order!), but the iterator was really straightforward. Pop the closest item from the queue; if it's an Octree node add all the children to the queue (frustum culled), if it's an Object return it. Match expressions really shine here.

It's also fast. Counting the time between starting the game and watching the last object pop in, the wasm implementation appears to be ~20-50% faster. Success.

Now for the difficult part: not losing interest in the project after finishing the proof-of-concept. :roll:

User avatar
Flumble
Yes Man
Posts: 2201
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Tue May 07, 2019 12:12 pm UTC

Can I get a smartphone (android/ios) to keep javascript and location services active while the screen is off? I'd like to track my (and friends') running and send it to a server in realtime, preferably from a webpage (stores are expensive and sideloading is hard) and without having the phone in drainage mode.

Most of what I found so far are stackoverflow questions of 5+ years ago.


Tub wrote:Now for the difficult part: not losing interest in the project after finishing the proof-of-concept. :roll:

The goal is the proof-of-concept, right? :mrgreen:

User avatar
Xanthir
My HERO!!!
Posts: 5398
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Tue May 07, 2019 3:09 pm UTC

Flumble wrote:
Can I get a smartphone (android/ios) to keep javascript and location services active while the screen is off? I'd like to track my (and friends') running and send it to a server in realtime, preferably from a webpage (stores are expensive and sideloading is hard) and without having the phone in drainage mode.

Most of what I found so far are stackoverflow questions of 5+ years ago.

No, you can't. It's a sensitive operation that we're not willing to allow a page to push into a background Service Worker and invisibly track you with; the page needs to be open and active to receive location data.

Native apps are just security/privacy nightmares.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Flumble
Yes Man
Posts: 2201
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Tue May 07, 2019 10:28 pm UTC

Xanthir wrote:No, you can't. It's a sensitive operation that we're not willing to allow a page to push into a background Service Worker and invisibly track you with; the page needs to be open and active to receive location data.

You standards people always ruin everything!!1! First you can't just retrieve a precise location without the user's permission, now you can't even track people whenever you like! :roll:

I guess I'll go with "keep your phone unlocked constantly" for now. The reason I want to send the position in real time in the first place, is so you can see each other on the map in real time, for which you'll need the screen turned on anyway. (Telling the relative distance would be neat too, but with that much overengineering I may as well put in the effort of turning it into a native program that can access the location in the background.)

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Coding: Fleeting Thoughts

Postby Xeio » Wed May 08, 2019 3:42 am UTC

I can't decide if this is beautiful or horrifying:

Code: Select all

private static string GetFullName(ClassDeclarationSyntax @class)
{
    string fullName = @class.Identifier.ValueText;
    SyntaxNode node = @class;
    while(true)
    {
        switch (node.Parent)
        {
            case NamespaceDeclarationSyntax @namespace:
                fullName = $"{@namespace.Name}.{fullName}";
                break;
            case ClassDeclarationSyntax outerClass:
                fullName = $"{outerClass.Identifier.ValueText}.{fullName}";
                break;
            default:
                return fullName;
        }
        node = node.Parent;
    }
}

Tub
Posts: 461
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Thu May 09, 2019 3:29 pm UTC

TIL that google will happily store and monetize all of your location data, but considers it a privacy problem when someone else does. :roll:

Xeio wrote:I can't decide if this is beautiful or horrifying:

It can be used for good or evil. I wonder, which is it?

Tub
Posts: 461
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Sat May 18, 2019 10:00 pm UTC

Tub wrote:It's also fast. Counting the time between starting the game and watching the last object pop in, the wasm implementation appears to be ~20-50% faster. Success.

I wasn't happy with this. A bit of benchmarking later, the mesh generation code has been improved by another +120% on top of the previous improvements.

I wouldn't know how to do these kinds of optimizations in a high level language (like JS) when targeting an unknown and changing environment (like a browser).

So my thoughts of the day are:
  • If you need speed, and you're willing to invest the time, wasm works.
  • Hash maps are at the core of most dynamic languages, used to implement objects. Lookups are O(1) and presumed to be really fast. However, when you're doing ~150.000 of them per frame, it helps to bring that number down, and it also helps to use a faster (but less secure) hashing function than the default one.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests