Files

Aryadev Chavali 38d531ca31 feat! Multithreading

commit a763bff532
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 04:33:13 2025 +0000

    Added release mode building

    Now the build script enables you to:
    - Build in debug mode (default no arguments)
    - Build in debug mode then run (`run` argument)
    - Build in release mode (`release` argument)

commit 7112937b0b
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 04:30:50 2025 +0000

    Better thread pool constructor

    statically define a number of threads, then setup the necessary
    machinery to make it work.

commit a5666328b7
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 04:29:32 2025 +0000

    Fixed the heap-use-after-free issue.

    Just standard multithreading stuff; access to the allocator while hot
    threads are running means stuff can change underneath us even /during/
    a read.  I've mutex locked state for stuff in the drawing domain which
    stops this issue.

commit 5d78cb20df
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 04:28:21 2025 +0000

    Adjust TODOs

commit 9d3a202c27
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 04:09:50 2025 +0000

    Implement stepping via KEY_SPACE

commit 424fab2e40
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 04:08:01 2025 +0000

    Weird bug in draw_tree

    Seems near the 100,000 node mark, the vector craps itself?  I keep
    getting "heap use after free" errors here when trying to access the
    allocator vector.  Disabling fsan just leads to a segment fault near
    the same point.

    I think we might need to introduce our own vector :)

commit 6ffa63f7ac
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 04:07:43 2025 +0000

    Make general delay 1ms

    Just for my puny eyes to see.

commit 2dbe3d0a58
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 03:54:30 2025 +0000

    merge generate_children into do_iteration

    Also fix this really weird slow down we get from doing direct mutation
    to a state.allocator.get_ref (i.e. a Node by reference).  Maybe the
    compiler just can't inline that instruction?  Regardless, this patch
    fixes the slow downs!

commit 7e801df280
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 03:53:51 2025 +0000

    no more numerics

commit f70517cf41
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Dec 12 03:08:56 2025 +0000

    Simplify mutex locking scheme (lock at start, unlock at end)

commit 00858cf74f
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Nov 28 17:24:33 2025 +0000

    Rewrite main to draw based on our new state/draw_state

    Arranges a thread set, draws based on draw_state.  No need to lock the
    mutex since drawing should only require reading.  Still has a timer in
    case we need to do timed checks.

commit 3e065e50a9
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Nov 28 17:24:12 2025 +0000

    Disable previous work

    We're going to rewrite this

commit ab0f152742
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Nov 28 17:23:05 2025 +0000

    Define `worker` function which a thread should run

    Pauses until state.pause_work is false (checking every
    THREAD_PAUSE_DELAY), then performs an iteration.  Quits when
    state.quit_work is true (based on loop).  Generally delays itself by
    THREAD_GENERAL_DELAY.

commit 014821ceb5
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Nov 28 17:22:39 2025 +0000

    Added booleans for thread workers to look at when running

    pause_work temporarily stops work, but should keep the thread alive.

    stop_work should kill the thread.

commit 1bd8a9f7b2
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Fri Nov 28 17:21:21 2025 +0000

    Add run component to build script, activated by passing argument `run`

commit 6f620644bf
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:57:10 2025 +0000

    Define constructors for state.hpp explicitly

commit 0008c31f53
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:53:10 2025 +0000

    Add src/worker.cpp to build pipeline

commit f8068c4a15
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:52:52 2025 +0000

    Implement the two worker functions

commit 66c56f2c15
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:51:41 2025 +0000

    Define thread safe worker functions for generating new children on the tree

commit 6247f2af49
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:44:23 2025 +0000

    Add src/state.cpp to the build pipeline

commit 40e07e03f2
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:42:24 2025 +0000

    Add mutexes to state for the queue and the allocator

    Our threads need to negotiate access and mutation to the two
    resources - we don't want them treading on each others toes when
    generating new child nodes /or/ when trying to remove/add work to the
    queue.  The former situation is particularly worrisome due to how weak
    the indexing system is with the allocator.

commit 0abd353368
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:30:35 2025 +0000

    Implement cw::state::DrawState::compute_bounds

commit 0ac316ada4
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:30:21 2025 +0000

    Define the general state of the sim (extract from main.cpp)

commit a03fa13a07
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:19:52 2025 +0000

    Implementation (copied from numerics)

commit ff9a2851d4
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:19:41 2025 +0000

    Switch to using i64's instead of optional u64 in Node

commit 6c2bc93874
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:12:35 2025 +0000

    remove index_t definition

    conflicts with prev code base.

    Also std::optional doubles the size of the underlying type.
    horrifying!  I don't want to have to give 16 bytes over for something
    that could be embedded in the 8 bytes of the u64 directly.  I'm
    thinking we could just use i64's instead, sacrificing that top bit to
    indicate if the value is present or not.

commit 7a4d158d2f
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 01:02:31 2025 +0000

    Add gcd to base.hpp

commit e032303773
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 00:56:45 2025 +0000

    Define node.hpp (move definitions away from numerics.hpp)

commit 9821a2ab15
Author: Aryadev Chavali <aryadev@aryadevchavali.com>
Date:   Thu Nov 27 00:55:44 2025 +0000

    Define basic type aliases and useful functions/macros for use throughout the system

2025-12-12 04:33:54 +00:00

3.6 KiB

Raw Permalink Blame History

Calkin-Wilf trees

A graphical visualisation of Calkin-Wilf trees.

Currently visualises it using a self adjusting number line, from the smallest fraction to the largest fraction generated. Both are always positive.

The bound fractions are drawn in white, while all other fractions are in red. On any one iteration (taking any one fraction and generating its two children fractions), the generated fractions are in blue while the generator fraction is in green.

This was done just for fun really, but it's quite fun to see it generate a dense number line over many iterations.

TODOs

TODO Tree visualisation

Instead of a number line, how about visualising the actual tree at work as a graph of nodes? Maybe colouring nodes based on where it is on the number line.

TODO Don't walk the tree everytime we compute_bounds

location

We already have the latest bound nodes so we're part-way through the tree. Just keep going down what we have so far surely? Even better, don't use nodes at all. Run with an index!

DONE Fix weird issue at past 100K nodes

std::vector seems to crap itself past 100K nodes - we keep getting heap-use-after-free issues when trying to access the allocator nodes at that point. Seemingly random. What's going on?

Solution: everytime we want to access the allocator for nontrivial (like memory reads) we need to lock the mutex. No two ways about it. All draw functions were causing the issue.

DONE Prettify code base

It's a big blob of code currently in the graphics portion. Not very pretty but it gets the job done. Try modularisation.

DONE Multithreading

Currently single threaded. A multithreaded implementation could have multiple nodes generated at once, which would speed up the implementation.

Might need to study my current implementation to see if it could be done better.

DONE Formalise state structure (separate drawing functions)

Make a dedicated header and fit the necessary functions to our state structure: state structure.

We need this in order so that we can get multithreading (using mutexes on the actual state itself) working.

A good working name would be cw_state.

We could then have a separate structure for the drawing context (cw_draw) which can update itself by reading the cw_state.

DONE Setup a queue and allocator mutex on state

We need one for the queue so we can make clean pushes and pops, and one for the allocator to ensure we're not messing up our indices in the nodes.

We could just set these up in the state structure itself to make lookup easier.

DONE Make iterate use the state structure and mutexes

[[file:src/numerics.cpp::std::tuple<Fraction, Fraction, Fraction> iterate(std::queue<word_t> &queue,]]

Locking scheme could be:
- Lock queue when popping a value as root, then unlock.
- Leave queue and allocator unlocked while getting root/left/right values (readonly) and computing (but not setting/allocating) the left and right node values
- Allocator Lock when allocating the left/right values, setting the root's left and right, then unlock.
- Queue lock when pushing the left and right fractions for further processing, then unlock
- Unlock all when returning relevant values

I think this scheme minimises the any mutex is locked to just the bare minimum, ensuring other threads can get in on the action.

3.6 KiB Raw Permalink Blame History