fmstephe
Repos
59
Followers
56
Following
24

Events

bytestore.Store.Alloc() returns the alloced []byte

Previously we returned (Pointer, error) but the error was always nil. We dropped the unused error, and now return the allocated []byte. This more closely matches the objectstore.Store api.

Adding stringstore package

This package allocs strings with very low GC impact using bytestore.Store and unsafe string<->[]byte conversions.

This is a base building block to build a low GC string interning package.

Created at 3 weeks ago
create tag
fmstephe create tag v1.0.0
Created at 3 weeks ago

Remove version from go.mod

Created at 3 weeks ago

Simplify type names in *store packages

Names like bytestore.ByteStore are now just bytestore.Store.

This is now possible since the different stores live in different packages.

Rename nextFree to rootFree for object/byte stores

This is the pointer to the first free slot/object in the store. This name distinguishes the root pointer to the free list from the internal linked list pointers, which are named nextFree.

Created at 3 weeks ago

Move ByteStore and ObjectStore into own packages

Because we intend to add more stores, like StringStore, this avoids the store package becoming crowded and hard to manage.

Created at 3 weeks ago

Changing all New() to Alloc()

This makes the counters clearer, the alloc count is just a count of the number of times Alloc() was called.

Adding *Stats structs for store package

These structs replace the existing individual AllocCount/FreesCount... methods and just collect all the statistics we collect for the stores.

Adding Reused stat in byte store tests

Add panics if an alloc() call is made with a bad size

We protect against allocs with sizes which are too large, these just can't be satisfied by a slab with a too small slot size.

We protect against allocs with sizes which are less than half of the slot size. These allocs can be satisfied by the slab, but is very space inefficient. This indicates an unrecoverable programming error in the ByteStore.

Remove out of date TODO comment

Created at 3 weeks ago

Fixed: freed slots were repeatedly allocated

Because we maintain the invariant that a freed slot's meta-data always has a non-nil 'nextFree' pointer, the last slot in the free linked-list points to itself. We were not checking for this case, and when freeing a slot we would simply copy the 'nextFree' from the freed slot straight to the 'nextFree' root in the byteSlab. This meant that the last freed slot would be allocated again and again (forever). Which is really bad.

Now we check for this case and set the 'nextFree' root to be nil when we free the final slot.

This was uncovered while writing extra tests. Although it's good that we found this bug, it was basically accidental and a very similar looking set of tests would have missed this very severe bug.

I think that some kind of fuzz based testing is really needed to generate a large corpus of more complex allocs/gets/frees than will be provided by hand-written unit tests. But that can come later.

Created at 3 weeks ago

Split byte_slab.go from byte_store.go

Previously byteSlab type was declared in byte_store.go file. As I wanted to develop some byteSlab specific tests I chose to split the implementation into a separate file, to keep the test->source file correspondence.

We added some byte_slab_test.go tests. Testing of byteSlab.free() is missing and will be included in a following commit.

Created at 3 weeks ago

Simplify small sized byte slabs

Previously we were lumping all allocations of size 0-8 into a single slab. This is a left-over of the unnecessary writing of the size of each slice into the byte data as a header.

Because there isn't any slab overhead in having slabs specifically set up to allocate small slices we can now do that.

Now we have a clean and straight forward slab for each power of 2 sized group.

Lower cased some error messages

Extended allocator slabs to cover all of uint32

This means that you can now allocate a slice of any size inside of uint32. Take care as allocating a single very large slice will create 1024 of those slots when allocating a whole chunk. If your allocation is 1 Gig we will now allocate 1024 Gigs for you. This needs to be fixed.

We created a separate function which initialises the slice of slabs. The slabs are now organised as follows:

0: The specialty 0 sized slab allocator 1: 2^0 sized slab allocator 2: 2^1 sized slab allocator 3: 2^2 sized slab allocator 4: 2^3 sized slab allocator ... 31: 2^30 sized slab allocator 32: 2^31 sized slab allocator 33: 2^32 - 1 sized slab allocator

The final allocator looks a bit odd, because you might expect it to be 2^32 sized, but 2^32 is 0 in a uint32, so we just take max-value here instead.

We removed the existing tests, which tested the lower level indexForSize functions and now we just test that the completely initialised slab slice is properly set up.

One observation that I made while writing and debugging the tests is that evenly distributed random numbers in uint32 are almost all very large numbers. This surprised me at first, but after some thinking I realised that almost half the numbers in a uint32 are larger than 2^31. Furthermore a solid majority of these numbers are larger than 2^30 and so on. There are just more large numbers than small ones if we group them into powers of two (like our allocator does). So we did some extra processing to ensure that our tests generate an even spread of large and small numbers across the powers of two groups that we care about.

Created at 4 weeks ago

Fixing errors in parcel_server

These were small changes made to ByteStore.

Created at 4 weeks ago

Added ByteStore.Free()

We have used the same meta-data based approach that we used in ObjectStore. However there was a complication, in that the offset which points into a slice of bytes can't be used to point into a slice of meta-data objects. So we now maintain two offsets, byteOffsets and slotOffsets.

One important thing to note, is that we removed the writing of the size of an allocation from the byte slices themselves. This piece of meta-data was unncessary because we were storing the size of a slice in the pointer. This significantly simplifies the implementation. One thing that's worth pondering here is that this was missed initially. There was never any reason to write the size into the slice itself, but this (in hindsight) observation was missed. This highlights the importance of full system comprehension in programming, if you start dropping details out of your brain, you are much more likely to produce over-complicated implementations, which are then even harder to keep inside your brain. Although this is a small error, and easily fixed, it feels like a warning. A likely worthwhile immediate step is a series of careful renamings, to ensure that at least this part is clear.

Created at 4 weeks ago

Added ByteStore.Free()

It is not yet fully tested and likely has a few bugs.

We have used the same meta-data based approach that we used in ObjectStore. However there was a complication, in that the offset which points into a slice of bytes can't be used to point into a slice of meta-data objects. So we now maintain two offsets, byteOffsets and slotOffsets.

Created at 4 weeks ago

Small tidy-up of object_store code

Added ByteStore.Free()

It is not yet fully tested and likely has a few bugs.

We have used the same meta-data based approach that we used in ObjectStore. However there was a complication, in that the offset which points into a slice of bytes can't be used to point into a slice of meta-data objects. So we now maintain two offsets, byteOffsets and slotOffsets.

Created at 4 weeks ago

Avoid pre-allocating byte chunks

Previously we were allocating an initial chunk - a slice of contiguous bytes that make up many slots for a slab.

Now we don't allocate any chunks, but build a chunk when the first allocation is made. This avoids unnecessary allocations of chunks that may never be used.

Created at 4 weeks ago

ByteStore now allocates from pre-sized byte slabs

These slabs are all power of 2 sized, although the first 4 bytes is used to record the size of the actual allocation. So for example, if you want to allocate 4 bytes, you will need at least an 8 byte sized slab to allow for the size to be written.

This approach is adopted to make it easier to free allocated byte slices. For this to be reasonably simple we would rather allocate and free from pre-sized byte slices.

The smallest slab used is 8 bytes, so 0, 1, 2, 3 and 4 byte allocations all use this smallest slab. The remaining slabs are simply successive powers of 2 in size, e.g. 8, 16, 32, 64, ...

The hardest part of implementing this was building a reliable mapping from allocation size to an index starting at 0 (so we could lookup a slab by index using the desired allocation size). Some subtle code was developed to achieve this, there may be a simpler way.

Created at 4 weeks ago

Separate meta-data from objects in ObjectStore

This is probably very slightly slower than storing the metadata right next to the objects. We make this change because it is a simpler implementation approach for the ByteStore. I would prefer to have both stores use the same implementation approach to start with. We can make specific optimisations later, if needed.

Created at 1 month ago

Rename lowgc_quadtree to quadtree

This is a much nicer package name.

Created at 1 month ago

Removing quadtree package

This package was preserved to act as a performance comparison to the lowgc version. However, the interface of the lowgc version is changing and the work overhead of maintaining this package doesn't feel worthwhile.

So we will drop it.

Created at 1 month ago

Objectstore.Free(ObjectPointer) method added

This method allows us to 'free' an object, this object can then be reused for future Get() calls.

To achieve this we added a very simple linked list wrapper to each object.

The ObjectStore itself has a pointer to a free object (this pointer may be nil). This pointer is called the root free pointer, all freed objects are reachable starting from the root free pointer and following the linked list.

When allocating a new object we first check to see if a previously freed object is available. If a freed object is available we return that and then set the root free pointer to point at the next object in the linked list (which might be nil).

We maintain an important property. Any freed object (which has not been re-allocated) has a non-nil pointer to another freed object. In the case where there isn't another freed object to point to, the freed object points to itself.

This allows us to test whether an object being accessed via Get is actually free. We can also test if an object being Free(ed) is already free. In both of these cases the method calls will panic.

After writing all of this code, we seem to have a mixture of terminology developing. We Get() a new object and then increment a field called allocs. This starts to feel confusing. We should try to tidy up the naming of these fields and methods in the future.

Created at 1 month ago

Upgrading to go 1.19

Created at 1 month ago

QuadTree.Survey func now returns a boolean

If the survey func returns false this terminates the survey. This is added to allow surveys which only return a limited number of entries.

Adding QuadTree.Tree.Count() method

This method gives a count of the number of elements within an area.

Map prototype now displays markers at high zooms

Created at 1 month ago

QuadTree.Survey func now returns a boolean

If the survey func returns false this terminates the survey. This is added to allow surveys which only return a limited number of entries.

Adding QuadTree.Tree.Count() method

This method gives a count of the number of elements within an area.

Map prototype now displays markers at high zooms

Created at 1 month ago

Fixing null json element bug

We had spelled null as nil.

Some small progress in the html prototype

Created at 1 month ago

Changing lowgc_quadtree.T to Tree

This seems like a clearer name for this type.

Also some minor tidy ups.

Created at 1 month ago

Adding leaflet introductory tutorial

https://leafletjs.com/examples/quick-start/

Created at 1 month ago

Using byte store to store all parcel data

Created at 1 month ago

Printing heap objects on each request

Created at 1 month ago

Ignore parcel_server binary

Created at 2 months ago

Changed View coordinate system

Previously we said that the view's coordinates conceptually started a 0,0 as the top left point of the positive coordinates.

This means that the left most x is lower than the right most x, which matches the standard way of drawing a graph from highschool. Which is fine.

But it also means that the top y coordinate is less than the bottom y coordinate i.e. the positive y coordinates start with zero at the top and grow downwards. This is the opposite of how you would draw a graph in highschool. It also matches badly with convenient mental models for latitude values, where higher values are north (up) and lower values are south (down).

The reason the previous coordinate system was chosen was because some graphics coordinate systems start with the top left corner of the screen being 0,0 and grow rightwards and downwards. This is fine for graphics, but we are specifically representing long/lat values here.

Adding validation to long/lat values

We now check that the long/lat values parsed in lds_csv are valid. This was added after we observed longitude values of ~183 which is outside the -180...180 range. It's likely that these outside values can be normalised by wrapping them around to -180. For now we just consider these values to be errors.

Quadtree.Insert() now returns an error

The error is not nil only if the x,y point for the insert is outside the View of the tree itself. In this case it's impossible to add anything into that point for this tree.

Created parcel_server

This is a very basic, very badly written, server which will send land parcels within a square sent in form fields. It responds with a json array of parcel documents found within that square.

Created at 2 months ago

Clarified RawCSVEntry.Error comment

We specify that the LineNum field is also set when the Error field is not nil.

Separated LineNum and Error from Parcel data

Previously the struct was called RawCSVEntry, which is a completely meaningless name. This struct had meta-data, line number and error mixed in with land parcel data.

Now we have ParcelData struct, which has the actual land parcel data. This is wrapped in a CSVParcelData struct. This struct has the line number and error meta-data along side the parcel data. This makes it clearer when we find an error in a csv line and we write the line number and the error data, but leave the parcel data zeroed.

Created at 2 months ago