# Questions for a new string type and on GC/alignment/padding

**URL:** <https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077>\
**Category:** General Usage\
**Created:** [December 20, 2016, 11:14pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077 "2016-12-20T23:14:51Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [December 20, 2016, 11:14pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077/1 "2016-12-20T23:14:51Z")

</div>

I’m trying to make a:

```julia
immutable New_String_Type <: AbstractString
         first::UInt64
         last::Union{String, UInt64}
end

```

This works, but really I want this to take 128 bits. Is that what happens and/or can I do:

```julia
immutable New_String_Type <: AbstractString
         first::UInt64
         last::String
end

```

And reinterpret the memory to overwrite first and last (I assume last is a 64-bit pointer), and expect the GC to overlook invalid pointer when I overwrite?

Is this somehow better?:

```julia
immutable New_String_Type <: AbstractString
         first::UInt64
         last::Union{Vector{UInt8}, UInt64}
end

```

* * *

```julia
julia> @edit a=String("P")
ERROR: expression is not a function call, or is too complex for @edit to analyze; break it down to simpler parts if possible
 in error(::String) at ./error.jl:21

```

I can locate, but is there a workaround for `@edit` here?

* * *

I see alignments, and jl\_value\_t (at least 16-byte, didn’t read carefully…) that I assume is an overhead for all objects, that is the target of the String pointer (not immutable itself).

```julia
http://docs.julialang.org/en/latest/devdocs/object.html

#define JL_SMALL_BYTE_ALIGNMENT 16
#define JL_CACHE_BYTE_ALIGNMENT 64
#define GC_MAX_SZCLASS (2032-sizeof(void*))

STATIC_INLINE jl_value_t *jl_gc_alloc_(jl_ptls_t ptls, size_t sz, void *ty)
{
    const size_t allocsz = sz + sizeof(jl_taggedvalue_t);
    if (allocsz < sz) // overflow in adding offs, size was "negative"
        jl_throw(jl_memory_exception);
    jl_value_t *v;
    if (allocsz <= GC_MAX_SZCLASS + sizeof(jl_taggedvalue_t)) {
        int pool_id = jl_gc_szclass(allocsz);
        jl_gc_pool_t *p = &ptls->heap.norm_pools[pool_id];
        int osize;
        if (jl_is_constexpr(allocsz)) {
            osize = jl_gc_sizeclasses[pool_id];
        }
        else {
            osize = p->osize;
        }
        v = jl_gc_pool_alloc(ptls, (char*)p - (char*)ptls, osize);
    }
    else {
        v = jl_gc_big_alloc(ptls, allocsz);
    }
    jl_set_typeof(v, ty);
    return v;
}

JL_DLLEXPORT jl_value_t *jl_gc_big_alloc(jl_ptls_t ptls, size_t sz)
{
[..]
    size_t allocsz = LLT_ALIGN(sz + offs, JL_CACHE_BYTE_ALIGNMENT);
    if (allocsz < sz) // overflow in adding offs, size was "negative"
        jl_throw(jl_memory_exception);
    bigval_t *v = (bigval_t*)malloc_cache_align(allocsz);

JL_DLLEXPORT void *jl_gc_managed_malloc(size_t sz)

typedef struct _jl_value_t jl_value_t;

struct _jl_taggedvalue_bits {
    uintptr_t gc:2;
};

struct _jl_taggedvalue_t {
    union {
        uintptr_t header;
        jl_taggedvalue_t *next;
        jl_value_t *type; // 16-byte aligned
        struct _jl_taggedvalue_bits bits;
    };
    // jl_value_t value;
};

    //struct jl_taggedvalue_t <>;
    union {
        uintptr_t header;
        struct {
            uintptr_t gc:2;
        } bits;
    };
    // must be 64-byte aligned here, in 32 & 64 bit modes
} bigval_t;

STATIC_INLINE void gc_time_count_mallocd_array(int bits)
{
    (void)bits;
}

```

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [December 20, 2016, 11:34pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077/2 "2016-12-20T23:34:26Z")

</div>

> [@Palli](#):
>
> This works, but really I want this to take 128 bits. Is that what happens and/or can I do:

It should be on 64bits platforms.

> [@Palli](#):
>
> or can I do:
> 
> immutable New\_String\_Type \<: AbstractString  
> first::UInt64  
> last::String  
> end

Absolutely not!

> [@Palli](#):
>
> Is this somehow better?:
> 
> immutable New\_String\_Type \<: AbstractString  
> first::UInt64  
> last::Union{Vector{UInt8}, UInt64}  
> end

Not sure what you are trying to do.

> [@Palli](#):
>
> I can locate, but is there a workaround for @edit here?

Are you trying to edit `=`?

> [@Palli](#):
>
> I see alignments, and jl\_value\_t (at least 16-byte, didn’t read carefully…) that I assume is an overhead for all objects, that is the target of the String pointer (not immutable itself).
> 
> …

Not sure if you are asking something or not. But I should at least correct that `jl_value_t` has zero size instead of 16.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [December 21, 2016, 12:45pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077/3 "2016-12-21T12:45:09Z")

</div>

[Since I’m new to Discourse, I assume there’s no answer from ihnorton to see. Maybe the pen icon under “P” means he’s writing one… This was my first post; can’t yet figure you how to quote and answer inline.]

Just to clarify; maybe I should have stated from the start.

I want to do:

immutable New\_String\_Type \<: AbstractString  
first::UInt64  
last::String  
end

and make a fast path for short strings. Bit[s] from first could indicate. Then if I could overwrite “garbage”, end-part of my 16-byte [ASCII] string in last, this would work.

“A type union is a special abstract type”

[It seems to me that a Union in Julia, has one more indirection, not like Union in C.]

In C something like this would work. Even with GC, if you add Boehm-style GC (non-moving, Julia also has, is that going to change, or do you think this would break already? Any meaningful bits in the pointer? Top of bottom bits special?):

[https://www.hboehm.info/gc/](https://www.hboehm.info/gc/)

Such strings, would be stack allocated in two 64-bit CPU registers, and only a heap access needed for longer strings, making average speed for strings faster.

There may not even be a speed vs. memory tradeoff. [On 64-bit, only considering for now] a string will always be half as short (excluding the heap part), but the pointer points to something, and that is I guess at least 64-bits because of alignment.

Does Julia have interned strings? With interned (or if I implement), I _might_ not win on space, but I guess I still do for speed.

I’m not sure, but before I thought:

immutable New\_String\_Type \<: AbstractString  
first::UInt64  
last::Union{String, UInt64}  
end

behaves as either:

immutable New\_String\_Type \<: AbstractString  
first::UInt64  
last::UInt64  
end

or

immutable New\_String\_Type \<: AbstractString  
first::UInt64  
last::String  
end

meaning you construct either, and type-inference assumes either? I’m probably wrong and I can use either (e.g. in an array of my new type). I can’t see how Julia can know which is used in each instance, except by an extra indirection to the heap.

@edit a=String(“P”)

I was looking at the “String(“P”)”-part, not =, yes, it looks like a function call but is a constructor with no real function. This isn’t a big deal…

---

<div class="post-metadata">

**Author:** ![ihnorton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihnorton/32/26_2.png) [@ihnorton](https://discourse.julialang.org/u/ihnorton)\
**Post date:** [December 21, 2016, 12:48pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077/4 "2016-12-21T12:48:19Z")

</div>

FYI: use `triple back ticks` to format your code, like GitHub.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [December 21, 2016, 1:42pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077/5 "2016-12-21T13:42:33Z")

</div>

> [@Palli](#):
>
> and make a fast path for short strings. Bit[s] from first could indicate. Then if I could overwrite “garbage”, end-part of my 16-byte [ASCII] string in last, this would work.

This I understand and this is what I said you should absolutely not do.

> [@Palli](#):
>
> I was looking at the “String(“P”)”-part,

The macro cannot figure this out for you, What’s the `a=` doing there.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [December 21, 2016, 3:34pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077/6 "2016-12-21T15:34:17Z")

</div>

“This I understand and this is what I said you should absolutely not do.”

To bad… but I really want to! [At least know for sure what will happen…]

I can still try and see Julia crash and burn… (or not if you think it wil lbe unpredictable). To be clear, are you saying that will happen, or this isn’t a good idea, because it works now, but, say, you want later to implement moving GC? There are ways around that; and for current non-moving (if not already implemented). I may give up, if I need to modify the C GC code… If this [seems to] works with 0.5.0 I’ll try to get a prove-of-concept.

Are you also saying, a) there isn’t (enough) upside for faster strings and/or better ways to do that? or b) not worth fixing the GC to handle? c) You don’t think the strings will actually be faster (too few small ones…?)

I could live with being forced to set the high (or low) bit of the pointer. Those pointers are likely never used. There would be a tiny slowdown in GC having to check first if there’s a legal pointer. I guess they’re all assumed to be legal?

How is Ptr{String} handled? Or rather just Ptr{CString}, are all CStrings assumed to be not handled by the GC? Would that be a workaround? [It seems then I would have memory leaks or having to implement reference cuonting for the strings…] If you can have arbitrary Ptr, it seems you must relay on either another legal GC pointer to your object, to prevent the object killed or be running uotside of the GC, as with (some) C API objects.

I guess I could go from 16-byte → 24-byte, for now, and only really have 16-byte strings then in the fast case. Then it would be really tempting to have the full 24-char…

Will 24-byte objects, when used be aligned to 32-byte, so I might as well go with that from the start?

> **[GitHub - JuliaArrays/StaticArrays.jl: Statically sized arrays for Julia](https://github.com/JuliaArrays/StaticArrays.jl)**
>
> Statically sized arrays for Julia. Contribute to JuliaArrays/StaticArrays.jl development by creating an account on GitHub.

or rather:

```julia
immutable New_String_Type <: AbstractString
         first::SVector{16,UInt8}
         last::String # Would Nullable{String} here, take extra memory in this object and/or extra indirection?
end

```

“What’s the a= doing there.”

Just an assignment… turned out to be my problem…

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [December 21, 2016, 4:11pm UTC](https://discourse.julialang.org/t/questions-for-a-new-string-type-and-on-gc-alignment-padding/1077/7 "2016-12-21T16:11:26Z")

</div>

> [@Palli](#):
>
> To be clear, are you saying that will happen, or this isn’t a good idea, because it works now, but, say, you want later to implement moving GC?

It’ll crash.

> [@Palli](#):
>
> Are you also saying, a) there isn’t (enough) upside for faster strings and/or better ways to do that? or b) not worth fixing the GC to handle? c) You don’t think the strings will actually be faster (too few small ones…?)

I’m not saying any of those. I can say now that I don’t think this is the right way to improve string handling.

`String` has nothing to do with `Cstring` or pointers.