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

General Usage
1

I’m trying to make a:

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:

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?:

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

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).

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;
}
2

It should be on 64bits platforms.

Absolutely not!

Not sure what you are trying to do.

Are you trying to edit =?

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.

1 Like
3

[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/

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…

4

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

1 Like
5

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

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

6

“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?

or rather:

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…

7

It’ll crash.

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.

1 Like