# Question about how to fix some efficient memory layout of large 1d-structures?

**URL:** <https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809>\
**Category:** New to Julia\
**Tags:** memory-allocation, data\_structures\
**Created:** [October 16, 2022, 5:46pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809 "2022-10-16T17:46:42Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 16, 2022, 5:46pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/1 "2022-10-16T17:46:42Z")

</div>

Hi,

I’m trying to figure out the “right way” to be declaring a few 1d-tables for my chess-engine, in julia, such that their memory-layout is as **space** -efficient as possible, and (b) fixed and never changes (i.e. the gc should never shuffle around any portion or even a whole table, for whatever reason).

Specifically the **requirements & specs** for any one of those tables are:

1. They can be huge in size, relative to total available ram on a computer (up to ~50% of ram, as a rough estimate, in total).

2. All tables are to be allocated and initialized at startup, of the engine, and will **never** change in size - just data _within_ tables might change (some will even have constant values, just for efficient lookups).

3. There will **only** be random-access to the tables, ever, (no looping in any regular manner). just indexed access to single entries at any given time, with no correlatation to previous indices.

…so given the above, I basically just need some kind of fixed 1d-array-structure, but with tight memory-layout (no need to grow / shrink or do other funky stuff), for being able to to access any entry with a given `key` like so… `entry = table[key]`.

I think this code probably summarizes, my attempts, so far, well enough…

```julia
using Formatting
using Printf
const fD = generate_formatter("%'d")

mutable struct Entry
    data0::UInt64
    data1::UInt16
end
function test()
    nEntries = 4
    table = Array{Entry,1}(undef, nEntries)
    #table = Vector{Entry}(undef, nEntries) # alternative, but really same thing
    for i = 1 : nEntries
        table[i] = Entry(i, i) # just fill with unique dummy-data, for testing
    end
    entrySize = sizeof(Entry)
    tableSize = sizeof(table)
    @assert tableSize == nEntries * entrySize "Unexpected: sizeof(table) != nEntries*entrySize ($tableSize!=$(nEntries*entrySize))."
    printfmt("size of table: {1} entries [{2} Bytes @ {3} B/entry]\n", fD(nEntries), fD(tableSize), fD(entrySize) )
    return table
end

```

This immediately results in a failed assertion…

```julia
ERROR: AssertionError: Unexpected: sizeof(table) != nEntries*entrySize (32 != 64).

```

…I was expecting, the stuct to not be tightly packed, but rather padded to some multiple of the struct’s largest component (`UInt64 = 8 Bytes` in this case). But why is it showing me 32 Bytes, for the Vector - are those “just” the size of the memory-pointers (64-bit, on my platform / OS)?  
When removing the assertion, everything is initialized, as I had anticipated, just the `sizeof(table)` doesn’t correspond to the actual size…

```julia
julia> test()
size of table: 4 entries [32 Bytes @ 16 B/entry]
4-element Vector{Entry}:
 Entry(0x0000000000000001, 0x0001)
 Entry(0x0000000000000002, 0x0002)
 Entry(0x0000000000000003, 0x0003)
 Entry(0x0000000000000004, 0x0004)

```

Just looking at the table-entries, clearly, the table has to have at least `size >= 40 Bytes`. Is there another way, to assert the actual size of a(ny) 1d-structure, in julia? If there isn’t any easy function for querying the size of the table, can I just assume, that it is `sizeof(entry) * nEntries` large (64 Bytes, in this case)? Or do I need to use some other construct, for this kind of requirement (fixed static 1d-tables)?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [October 16, 2022, 7:31pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/2 "2022-10-16T19:31:31Z")

</div>

I think a vector (what you used) is what you want.

Do you need the entries to be mutable?

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 16, 2022, 11:30pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/3 "2022-10-16T23:30:13Z")

</div>

yes, there are some tables, that start empty, but are only being filled during run-time, so the individual entries need to be mutable, just the structure (number of entries, total) won’t change. And yes, a vector seems like the most suitable simple structure. 👍

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [October 17, 2022, 12:10am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/4 "2022-10-17T00:10:43Z")

</div>

The entries don’t need to be mutable for the array to be mutable, you can fill the array and replace entries by new immutable entries. I’m not completely sure, but in general that is preferable in terms of performance.

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 17, 2022, 12:20am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/5 "2022-10-17T00:20:06Z")

</div>

yes, the array will not be mutable, just the entries. And any structure, which ensures, that the entries (mutable or not) stay in their designated memory-spots should be performant. If I could, I would staple each entry to an address. 😅

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 17, 2022, 4:02am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/6 "2022-10-17T04:02:09Z")

</div>

you should make the elements immutable and just replace them. Julia won’t store mutable elements of an array inline because different references to a mutable object must have the same memory address. this will work out because by using immutable element types, the compiler won’t allocate memory when you create new ones and it should get optimized to a mutation of the enemy in the array by the compiler.

---

<div class="post-metadata">

**Author:** ![ToucheSir](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/touchesir/32/14411_2.png) [@ToucheSir](https://discourse.julialang.org/u/ToucheSir)\
**Post date:** [October 17, 2022, 5:47am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/7 "2022-10-17T05:47:58Z")

</div>

If you can live with the caveats in [Some counterintuitive behaviors · StructArrays](https://juliaarrays.github.io/StructArrays.jl/stable/counterintuitive/#Modifying-a-field-of-a-struct-element), StructArrays.jl could be another option.

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 17, 2022, 6:23pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/8 "2022-10-17T18:23:24Z")

</div>

Wow, I didn’t expect it to be so complicated, getting some datastructures instantiated, that _should_ really be extremely simple. But it turns out, I’m running into error after error… 😬

So I got some sort of rudimentary hashtable-code up and running, for my chess-engine…

```julia
using Formatting
using Printf
import Base: length
import Base.@propagate_inbounds

const fF = generate_formatter("%5.3'f") # format for typical float-output (3-digit-prec after .)
const fD = generate_formatter("%'d") # format for typical decimal-output (with 1000s-sep)
const fH = generate_formatter("0x%016x") # format for typical hex-output
const SI(x) = formatted(x, :SI, ndigits=4) # scientific not. (kilo, mega, ...)

mutable struct HashTable{T}
    entries::Vector{T}
    size::UInt64
    hashKeyMask::UInt64
    function HashTable{T}(n::UInt64) where T
        @assert checkPow2(n) "Spec-mismatch: size is not a pow of 2 (size= $size)."
        en = Vector{T}(undef, n)
        new(en,n,n-1)
    end
end
function length(ht::HashTable) return ht.size end
function checkPow2(v) return ( (v & (v-1))==0 && v>0 ) end
function hashKey2Index(ht::HashTable, hashkey) return (hashkey & ht.hashKeyMask) + 1 end
@propagate_inbounds function putForced(ht::HashTable{T}, hashkey::UInt64, entry::T) where T
    # no checking for collisions - potential overwrite...
    ht.entries[hashKey2Index(ht, hashkey)] = entry
    nothing
end
function get(ht::HashTable{T}, hashkey::UInt64) where T
    index = hashKey2Index(ht, hashkey)
    @inbounds return ht.entries[index]::T
end

```

…so far so good…  
Then I made a function `setupTable(...)`, which actually creates a (preinitialized) hashtable for me.  
(Note: I’ve, for now, fallen back to just using `UInt64`s as my ht-entries. Just to make stuff simpler and not have _another_ struct in the array, of the mutable struct `HashTable`…  
…also, because I don’t really understand, whether those entries should then be mutable or immutable - I’ve read so much, now, but it still really doesn’t make sense to me, how to change immutable elements.

```julia
function setupTable(sizeInBits, default)
    tableSize = 1 << sizeInBits
    entrySize = sizeof(UInt64)
    nEntries = (tableSize ÷ entrySize) % UInt64
    table = HashTable{UInt64}(nEntries::UInt64)
    for i = 1 : nEntries
        # init just with dummy-data, for getting it to work...
        putForced(table, i, (default + i)%UInt64)
    end
    tableSize = nEntries * entrySize
    @assert nEntries > 0 "Tablesize to small => 0 elements fit."
    printfmt("size of table {1}: {2} elements [{3} bytes @ {4} B/el.]\n"
            , SI(tableSize), fD(nEntries), fD(tableSize), fD(entrySize) )
    return table
end

```

…but even with all these simplifications, which are still quite a bit away, from the problem, I tried to understand earlier - I _still_ don’t even get this simple variation to work, when I try to create a bunch of these Hashtables and put them into a StaticArray, to perform some benchmarks and comparisons on them (with different sizes)…

This snippet…

```julia
# maxSize: In bits -> 20=1MB, 30=1GB, etc.
function tables1(maxSize, default::UInt64)
    tmp = Vector{HashTable{UInt64}}(undef, maxSize)
    for i = 12 : maxSize
        tmp[i] = setupTable(i, default)
    end
    # construct SVector, explicitly from the 21 HashTables in tmp
    tables = SVector{maxSize, HashTable{UInt64}}(tmp)
    return tables
end

```

…was supposed to produce 21 `HashTables` for benchmarking, but it yields an error, and I don’t understand, why…

```julia
julia> test = tables1(30,0x80000000000)
size of table 4.096k: 512 elements [4,096 bytes @ 8 B/el.]
size of table 8.192k: 1,024 elements [8,192 bytes @ 8 B/el.]
size of table 16.38k: 2,048 elements [16,384 bytes @ 8 B/el.]
size of table 32.77k: 4,096 elements [32,768 bytes @ 8 B/el.]
size of table 65.54k: 8,192 elements [65,536 bytes @ 8 B/el.]
size of table 131.1k: 16,384 elements [131,072 bytes @ 8 B/el.]
size of table 262.1k: 32,768 elements [262,144 bytes @ 8 B/el.]
size of table 524.3k: 65,536 elements [524,288 bytes @ 8 B/el.]
size of table 1.049M: 131,072 elements [1,048,576 bytes @ 8 B/el.]
size of table 2.097M: 262,144 elements [2,097,152 bytes @ 8 B/el.]
size of table 4.194M: 524,288 elements [4,194,304 bytes @ 8 B/el.]
size of table 8.389M: 1,048,576 elements [8,388,608 bytes @ 8 B/el.]
size of table 16.78M: 2,097,152 elements [16,777,216 bytes @ 8 B/el.]
size of table 33.55M: 4,194,304 elements [33,554,432 bytes @ 8 B/el.]
size of table 67.11M: 8,388,608 elements [67,108,864 bytes @ 8 B/el.]
size of table 134.2M: 16,777,216 elements [134,217,728 bytes @ 8 B/el.]
size of table 268.4M: 33,554,432 elements [268,435,456 bytes @ 8 B/el.]
size of table 536.9M: 67,108,864 elements [536,870,912 bytes @ 8 B/el.]
size of table 1.074G: 134,217,728 elements [1,073,741,824 bytes @ 8 B/el.]
ERROR: UndefRefError: access to undefined reference
Stacktrace:
 [1] getindex
   @ .\array.jl:924 [inlined]
 [2] macro expansion
   @ C:\Users\rober\.julia\packages\StaticArrays\PUoe1\src\convert.jl:212 [inlined]
 [3] unroll_tuple
   @ C:\Users\rober\.julia\packages\StaticArrays\PUoe1\src\convert.jl:207 [inlined]
 [4] convert
   @ C:\Users\rober\.julia\packages\StaticArrays\PUoe1\src\convert.jl:199 [inlined]
 [5] SVector{30, Vector{HashTable{UInt64}}}(a::Vector{HashTable{UInt64}})
   @ StaticArrays C:\Users\rober\.julia\packages\StaticArrays\PUoe1\src\convert.jl:169
 [6] tables1(maxSize::Int64, default::UInt64)
   @ Main .\Untitled-2:58
 [7] top-level scope

```

…creation of the ht is effortless, even at large sizes, but I don’t understand, what kind of `undefined reference` the static array is complaining about?  
The constructor-signature seems to match, what I’ve found, elsewhere, in a (toy-) example?

```julia
v2 = SVector{3,Float64}(1, 2, 3) # length 3, eltype Float64

```

Since it didn’t work, I also tried this macro-variant of creating a `SVector`, like this…

```julia
function tables2(maxSize, default::UInt64)
    # try with a macro
    tables = @SVector [setupTable(i, default) for i = 10 : maxSize]
    return tables
end

```

…which gives me a compile-time-error:

```julia
ERROR: LoadError: UndefVarError: maxSize not defined
Stacktrace:
 [1] top-level scope
   @ none:1
in expression starting at Untitled-2:64

```

Interpolating `maxSize` with a `$` then gives this error…

```julia
ERROR: LoadError: syntax: "$" expression outside quote
Stacktrace:
 [1] top-level scope
   @ none:1
in expression starting at Untitled-2:64

```

😬🤦‍♂️

Edit: Admittely, I’ve resorted to guessing, only, now - but I feel like I have no clue, what is going on - when all I wanted, was to allocated some simple block of memory, for some extremely simple array of primitive data-types. 🤔

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [October 17, 2022, 6:58pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/9 "2022-10-17T18:58:58Z")

</div>

In my _really_ humble opinion, you are overcomplicating things that should be simple, perhaps because of trying to translate the implementation from another language. Your original list of tables I would create like this:

```julia
julia> struct Entry
           data0::UInt64
           data1::UInt16
       end

julia> hash_table_list = [Vector{Entry}(undef,10) for _ in 1:21];

julia> hash_table_list[1][1] = Entry(1,1) # set some entry
Entry(0x0000000000000001, 0x0001)

julia> hash_table_list[1][1] = Entry(1,2) # replace entry
Entry(0x0000000000000001, 0x0002)

```

where the “10” there is the length of the tables.

That data structure is compact. The _immutable_ part is that of the entries, the rest (the containers) can be mutable and won’t affect performance much.

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [October 17, 2022, 6:59pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/10 "2022-10-17T18:59:43Z")

</div>

Perhaps you can explain a bit more about the particular use these 1D arrays will require - then you can dispatch on them based on specific properties you want them to have.

If you want your `Entry` to represent subsequent chessboards, maybe a Run Length Encoding technique could work.  
If you’re `Entry` are historical pro chess moves, you don’t need to consider the entire universe of possible chess boards, but a reduced subset of them that may permit a more compact encoding.  
If you only need to process the `data0` fields at a time, putting them in a `StructOfArrays.jl` type `Vec` could yield good benefits.

But these all depend on what you specifically need. Fortuntately a custom array and dispatching on it is the Julia creed.

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 17, 2022, 7:56pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/11 "2022-10-17T19:56:10Z")

</div>

thx for your response.  
As much, as I understand your curiosity and willingness, to embark in thoughts about the _content_ of data-entries in the arrays. There is literally _nothing_ uncertain about that part, for me. I am merely trying to implement efficient containers to store and retrieve individual data-elements and I’m happy, opening another thread, explaining all the details of the content, but for the sake of the questions I posted here, and for solving the issues I’m having, the content is literally irrelevant. 😉

I’m happy giving some background, though, just to motivate, why I’m even needing these containers.

- One Container / Hashtable (the largest) will be a a [transposition-table](https://en.wikipedia.org/wiki/Transposition_table), storing some of the positions, encountered in the search-tree, of what is, essentially a (much refined) [alpha-beta - search](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning). But since there will be a few M nodes being visited, during the search, within short time-spans (seconds), only a portion of those positions will make it into the hashtable (those, which belong to the currently best evaluated line, for either side, and which have the highest chances, enabling the pruning of the search-tree in other parts of the tree, but which also traverse the same position). The encoding of “position” is achieved via [zobrist-hashing](https://en.wikipedia.org/wiki/Zobrist_hashing), which can be generated much faster, than any run-lenght encoding, etc., and serves as the hash-key (index into the table), _at the same time_. You can find a rough sketch, of how entries in the transposition-table will look like, in [this post](https://discourse.julialang.org/t/question-about-functors-and-closures-i-think-with-an-example-but-really-a-general-q/88758/20). Overall, the hashtable is a global structure, where entries are persistent, even across moves, as positions are sometimes precalculated at great depth and their evaluation might stay relevant _or_ they may even reoccur (due to move-ordering, especially in phases of the game, with few captures).

- The above mentioned **Zobrist** -hashing is being calculated by having ~750 pre-computed (random) numbers, one for each piece on every square: 64 sq. x 2 colors x 6 types of pieces = 768 + castling-rights and a few other details. When a move is being made (simulated in the search!), the current’s position zobrist-hashkey is simply xor-ed with 2…3 of those numbers. One for the piece, leaving a sq., one for the same piece, moving to another sq. + potentially one more, for the latter target-square & a potentially captured piece, in case it is a capturing move. Etc.  
These keys are also stored in a lookup-table. In this case, it is a very small table (~750 x 8 bytes = ~6 KB). Kind of a lookup-table for the building-blocks of hashkeys to the first table. 😉

- Then there are other hashing functions, being used, especially for the move-generation of sliding pieces (rooks, bishops, queens), which are (like the zobrist-hashkeys) pre-computed and being looked-up, during a game-tree-search, for quick move-generation. See [here](https://www.chessprogramming.org/Magic_Bitboards#Fancy), especially, for a good intro, into _fancy magic bitboards_, which can be understood in terms of [minimal perfect hash-functions](https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function). Those tables are still much smaller, than the transposition-table, but do exceed L1-cache & L2-cache, even on modern machines, sadly, still. (~820 KByte).

- Those are probably the most prominent tables, but then there are a bunch of others, acting as parameter-lookups for positonal bonuses of pieces (depending on their board-position) or even whole arrangements of piece-ensembles (like pawn-structures, etc.). But this data is more flexible, to either be coded or for pre-computed data to be looked up. It is essentially always a tradeoff between costs of calculations and costs for alternative lookups in precomputed tables. Interestingly, this tradeoff itself is usually a parameter, which can be tuned, according to certain criteria. For example, a transposition-table can often speed up search by a almost a factor 4…5x, in the endgame, but it is only marginally useful, in the opening, etc., etc.

- A whole other story are [Endgame tablebase - Wikipedia](https://en.wikipedia.org/wiki/Endgame_tablebase). I think, at the moment, they are still working on 8-piece-endgame - tablebases, but this might get solved, in the foreseeable future, but this is not, what I’m trying to do here. I _will_ eventually support endgame-tablebases, and I’m sure, I’ll also provide a cache for _some_ of that data, but they will have to reside on disk, as even the (“only”) 6-piece-tables are ~150GB large - and this is with some very efficient encoding, already. 😉

…I hope, that helped motivating my efforts a bit.

For the questions, I’m having, regarding implementing a _general_ structure, of such tables, in julia: ALL access, to those tables will only ever be random, i.e. no iteration of entries, in any way. No calculation (like matrix-multiplication, broadcasts, or whatnot) Just plain access to individual entries of 1d-tables via their unique index. There is really not more to say, about it. Only read-access, in some cases, Read-write, in others.

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 17, 2022, 10:42pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/12 "2022-10-17T22:42:12Z")

</div>

> [@lmiq](#):
>
> In my _really_ humble opinion, you are overcomplicating things that should be simple, perhaps because of trying to translate the implementation from another language. Your original list of tables I would create like this:
> 
> ```julia
> julia> struct Entry
> data0::UInt64
> data1::UInt16
> end
> 
> julia> hash_table_list = [Vector{Entry}(undef,10) for _ in 1:21];
> 
> julia> hash_table_list[1][1] = Entry(1,1) # set some entry
> Entry(0x0000000000000001, 0x0001)
> 
> julia> hash_table_list[1][1] = Entry(1,2) # replace entry
> Entry(0x0000000000000001, 0x0002)
> 
> ```
> 
> where the “10” there is the length of the tables.
> 
> That data structure is compact. The _immutable_ part is that of the entries, the rest (the containers) can be mutable and won’t affect performance much.

you’re absolutely right, I somehow made it much more complicated, than it had to be.  
It’s not really, because of porting from another language - the allocation in java is basically a (trivial) one-liner, but all that mutable / immutable - StaticArray - hocuspocus just got me confused, I think - even more so, since I knew, that all I want is just allocate a block of 1d-memory! 😅  
After your example, though, I have a pretty simple example running (a bit more complicated, as I now already have a hashtable-struct with some logic, but that all works very well.  
Have run some test-benchmarks over 1M mutations of entries and 0 allocations. 👍  
Just started a (batch-) benchmark over a couple of those tables (at different sizes and with linear vs. random access to see, if I can eyeball-validate the structures working in memory as expected, when I can see them performing worse, as soon, as their sizes exceed the cache-limits of the various stages… Will post some pic, here, later, likely.

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [October 17, 2022, 11:09pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/13 "2022-10-17T23:09:42Z")

</div>

@fins

This may help:

```julia
struct Foo
   a::Int64
end

mutable struct Foo2
    a::Int64
end

isbits(Foo(1)) ## true
isbits(Foo2(1)) ## false

```

So if you make an array of a mutable struct that “isbits” it’ll just be a big block of memory, and that’s what you want.

If it’s an array of mutable structs… it’ll be a big block of memory containing pointers… and the actual data is stored in the heap somewhere.

That’s so that you can do something like

```julia
a = myarray[123]
push!(myarray,MyStruct(...))

a.myfield = 1

```

the `push!` might cause the array to have to allocate a new big block of memory and copy over the old contents… if it does that and a is a “pointer to the old location” then when you mutate a you’ll be mutating old data.

If you can’t mutate the struct then a = myarray[123] can just be basically copying the entry at 123 onto the stack.

Of course although the structs are immutable, it doesn’t mean you can’t change what’s in the array! you can change the entries of the array! so

```julia
myarray[123] = MyStruct(...)

```

is fine, because you’re replacing the struct at 123 with a new struct. Under the hood the compiler is just changing the bits.

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 17, 2022, 11:49pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/14 "2022-10-17T23:49:13Z")

</div>

> [@dlakelan](#):
>
> This may help:
> 
> ```julia
> struct Foo
> a::Int64
> end
> 
> mutable struct Foo2
> a::Int64
> end
> 
> isbits(Foo(1)) ## true
> isbits(Foo2(1)) ## false
> 
> ```
> 
> So if you make an array of a mutable struct that “isbits” it’ll just be a big block of memory, and that’s what you want.
> 
> If it’s an array of mutable structs… it’ll be a big block of memory containing pointers… and the actual data is stored in the heap somewhere.

Thx! That really helps - I remember looking at some objects with `isbits(...)` a while ago and not being able to quite understand, what it was really telling me (despite a clear description in the docs). But it might be, because I didn’t realize the consequences, at the time, what it means, when some object (i.e. a mutable struct) yields `false`. It got likely buried under so many layers of abstract vocabulary, that I discarded it as meaningless - since everything is bits, on a computer, literally (including pointers).

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [October 17, 2022, 11:53pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/15 "2022-10-17T23:53:39Z")

</div>

yes everything is made of bits, but isbits(x) means it can be shoved into an array or stuck on the stack. If it’s not isbits(x) then it’ll get allocated on the heap and track the object with pointers… that’s more or less my understanding… remember I was in the same place you are like in 2019-2020 and so I’m trying to pull you up along with me, but we both are probably making mistakes 😉

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 17, 2022, 11:54pm UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/16 "2022-10-17T23:54:30Z")

</div>

Yeah, the name `isbits` isn’t great, but it basically means that there aren’t any pointers hierarchically in the struct.

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 18, 2022, 12:16am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/17 "2022-10-18T00:16:04Z")

</div>

no worries - names are to be learned and as long as the semantics fit and are relevant, I’ll learn it. 😅

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 18, 2022, 12:25am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/18 "2022-10-18T00:25:13Z")

</div>

![image](https://global.discourse-cdn.com/julialang/original/3X/9/7/97882fa10fd1ebccf7110e063cf8d95d8c62736e.png)

…kind of funny, as I produced a svg-output with Gadfly, but had to make a jpg-screenshot, to upload.  
…but being able to quickly do stuff like this, was definetly one of the reasons, why I went for julia. 😉

---

<div class="post-metadata">

**Author:** ![fins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fins/32/43444_2.png) [@fins](https://discourse.julialang.org/u/fins)\
**Post date:** [October 18, 2022, 12:29am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/19 "2022-10-18T00:29:46Z")

</div>

What’s interesting, is, that one can find the cache-capacities of L3-cache, quite clearly (I have 4MB L3), but the other 2 (L1 & L2) don’t really show any distinct drop in performance, when the tables exceed those. Not sure, I overlooked something, but still interesting.  
My L1: 32KB (only data-cache) & L2: 512KB (per core, each, while L3 is shared between all cores).

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 18, 2022, 12:37am UTC](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809/20 "2022-10-18T00:37:06Z")

</div>

What’s your benchmarking code? If it has too much overhead, it might be hard to see the difference.

[Next page](https://discourse.julialang.org/t/question-about-how-to-fix-some-efficient-memory-layout-of-large-1d-structures/88809.md?page=2)