https://www.joelonsoftware.com/2001/12/11/back-to-basics/

https://v8.dev/blog/pointer-compression :-)

from the link :

The tag bits serve a dual purpose: they signal either strong/weak pointers to objects located in V8 heap, or a small integer. Hence, the value of an integer can be stored directly in the tagged value, without having to allocate additional storage for it.

V8 always allocates objects in the heap at word-aligned addresses, which allows it to use the 2 (or 3, depending on the machine word size) least significant bits for tagging. On 32-bit architectures, V8 uses the least significant bit to distinguish Smis from heap object pointers. For heap pointers, it uses the second least significant bit to distinguish strong references from weak ones:

15 years ago : http://www.and.org/vstr/comparison lists 28 string libraries. I don't see any with a similar pointer trick.

Unless I'm missing something, the benefit of type 1 is so low that differentiating between it an type 2 is almost certainly going to require more code than the single bytes saved in each string.

However, if you keep type 1 then you need to bulletproof implementation that will recoup the cost of the extra code needed in only a couple dozen strings. However, if you have dozens of strings then it's unlikely to be a small program making the savings moot. Finally, if you every merge a type 1 and 2 then the code for that is going to require you to use hundreds of type 1 strings to recoup the savings. It would be logical do do away with type 1 as it's almost certain that type 2 strings will be used for a "how to use this program" aka "--help" string.

The cost for having both type 1  and 2 is a few mask & shift operations.

inline int aStr_length_fast(aStr_t p) {
  uint32_t *q =  (uint32_t *)(p & ~3);
  int LSB =  p &  3;
  return (*q) & ~((~0) << (LSB<<3));
}

This works for types 1 , 2 and 3 (with type 3 limited to 24b/16M).

The problem is that you have to do it for all the functions. It may only require a handful of operations but when it's in multiple functions, you start needing dozens of strings to balance the space savings.

@Gravis  OTOH don't you already have to call strln() at these places ?

In modern OoOx CPUs (since the Pentium III) what costs time is random memory accesses and execution flow breaks (calls, jumps, conditional branches in particular).

In the above case, there is no branch, and memory access is to the very same cache line (by construction) so there is only a marginal cost.

@Yann Guidon / YGDES 

There is more to programming than ye olde C strings. There are C++ strings and NT has the UNICODE_STRING type. The days of relying on strlen are long gone.

@Gravis  I know this well, what is your point ?

https://en.wikipedia.org/wiki/String_(computer_science)#Representations

https://en.wikipedia.org/wiki/Comparison_of_programming_languages_(string_functions)

The last link compares about 50 languages.

Furthermore, the class of applications I try to address, including the constraints, is probably not well stated. I swap between many projects and drop ideas here and there...

@Yann Guidon / YGDES 

"if you keep type 1 then you need to bulletproof implementation that will recoup the cost of the extra code needed in only a couple dozen strings. However, if you have dozens of strings then it's unlikely to be a small program making the savings moot." - Me

"The cost for having both type 1  and 2 is a few mask & shift operations." - You

"The problem is that you have to do it for all the functions." - Me

The point being that the benefits of type 1 are outweighed by it's requirements.

You went on about needing strlen and I pointed out that that's no longer the case as many string implementations exist that hold the length of the string making the benefit a moot point.

@Gravis 

"many string implementations exist that hold the length of the string making the benefit a moot point."

FORTH calls them "counted strings" and these were already well accepted in the 60s (before PDP-7 dwellers at Bell Labs selected null-terminated for their pet project and language). That's also called "Pascal style" and certainly something else by other languages.

So yes there are many string implementations, I never pretended inventing them. Now, maybe you don't have to interact with POSIX often, or related tools or interfaces.

Due to alignment, Type 1 provides a marginal benefit, but what would you do with a byte prefix instead ?

The project is not as documented and elaborated as some of my other projects so you might miss some context and other elements. At least there is preliminary example code and I'm working on more elaborated features. They probably don't fit your needs and you are luckily not affected by the tyranic anachronism of <string.h>, and that's good for you.

@Yann Guidon / YGDES 

I'm more acquainted with POSIX than you may have thought. There are many POSIX compatible implementations already and there is literally no need to rely on POSIX string functions.

Here's the description for the "Better String" library: https://github.com/websnarf/bstrlib/blob/master/bstrlib.txt

If nothing else, you could use bstrlib as a better starting point.

@Gravis 

Thanks for the link ! And I presume nothing about your skills and knowledge.

"there is literally no need to rely on POSIX string functions."

I'd have a few things to say about this but I'll try to stay on-topic.

Of course I know I'm not the first one to complain about strings. I didn't know Paul's lib, which has not taken over the traditional libs yet. His author Paul Hsieh is not a mere beginner as I used to read him on c.l.a.x back in the Usenet days. I also used his references for x86 asm optimisation and followed his exploration of hashing algos. So I have deep respect for him.

Now let's simply read the link you sent :

"

A bstring is basically a header which wraps a pointer to a char buffer. Lets start with the declaration of a struct tagbstring:

struct tagbstring {
int mlen;
int slen;
unsigned char * data;
};

"

OK that's it, just like in almost every other HLL or interpreter. Delphi adds a refcounter, but so far nothing breathtaking:

* you have to carry a whole struct around, which is less convenient to return from a function than a plain pointer,

* constant strings have mlen=slen,

* the pointer uses 4/8 more bytes to the struct,

* the effort is mostly the same,

* and it adds one level of indirection.

I'm sure Paul's work is a few leagues above mine and he takes a reasonable idea to turn it into a great piece of code that I'd be happy to see integrated into POSIX for example. But you failed to convice me and, replying to

"you could use bstrlib as a better starting point."

I know it's better than standard C (and there is quite a lot to get inspiration from) but I see no benefit over the aligned strings. And it's not a NIH syndrome.

@Yann Guidon / YGDES 

"you have to carry a whole struct around, which is less convenient to return from a function than a plain pointer,"

What are you talking about? It's a pointer to a struct. Your stuff can be represented the exact same way. You're giving me the feeling that you don't quite grasp how compilers deal with structs.

@Gravis 

"You're giving me the feeling that you don't quite grasp how compilers deal with structs."

Feelings are treacherous. The C syntax allows it and it opens a whole can of worms. If it could, should you? You know C's x86 ABI returns the function's result in EAX (or RAX), which clearly can't fit a struct. You can and will play around. Each compiler will do their own thing, copying or dereferencing, sometimes in inefficient or unexpected ways. Whether it returns a pointer (to a struct allocated where ?) or bulk data (that are filled/copied where?) creates secondary issues.

Funnily, I used to decompile and single-step binaries generated from Ada-like VHDL (have a deep look at GHDL) and that crazy language family has no problem returning a struct or more, using other techniques even on a GCC backend. It makes me feel "too tight" when I must code in C again.

"It's a pointer to a struct. Your stuff can be represented the exact same way."

No.

Read again:

struct tagbstring {
int mlen;
int slen;
unsigned char * data;
};

Now:

typedef struct {
  uint32_t allocated __attribute__ ((aligned (8)));
  uint16_t len;
  char text[];
} Flex_aString_16;

You should see that "text" is not a pointer, it's the start of the array, using C99's "Flexible array" notation, that was indeed designed for this purpose. No indirection. You can printf() the pointer directly with a simple (char*) cast to the value, which points to Flex_aString_16.text. The pointer is self-sufficient and that's the whole point.

OTOH, compilers have to align, sometimes more than required so the saving of Type1 is almost irrelevant but it keeps compatibility with some other format.

And with the forced alignment the savings are not huge and only for size=4n+3

If you dropped type 1, what would you use if for ? I think I have covered the bases so far.

Honestly, I think you are attacking the wrong problem. Strings aren't really a problem when it comes to memory with the exception of very special programs. I would say the real issue is efficient allocation and management of memory pools in order to minimize memory fragmentation.

@Gravis  I agree that memory allocation is a huge .... "problem" doesn't even come close to the scale of this catastrophic mess.

I'm working on it too, already.

@Yann Guidon / YGDES 

Then you should look at "two-level segregated fit" because it's a good solve. You will need to be exceptionally clever to make an allocation method that could even compete with it.

I started to work on another aspect/side of the problem.

Hello word world!

Welcome !

Right now I write example code and the primary functions, to be uploaded here soon.

https://www.youtube.com/watch?v=Qyn1qxi73u8

Even Dave's Garage is talking about this obsolete dumpster fire...

I'm back on the subject, dudes ! With more hindsight and it's slowly coming together...

Why not just use a 16-bit length field all the time and avoid the complexity of deciding whether which variant it is, in return for wasting one byte? What you lose in data space you may save in code space.

this would be possible if the context was well confined in a language framework for example (such as Python, JS and others).
In Delphi for example, there is a 32b prefix but everything is aligned.

In my case I want to perform operations that differ from the safe&sane environment of managed languages and I want to avoid "shifting" blocks all the time. I want to do thing "in place" as much as possible. So the byte prefix is useful BUT often not large enough. 2 bytes forces alignment of the start of the character area.

I'll have to write a log about the use cases & environment...

Notes for later : Some random googling and readings...

https://en.m.wikipedia.org/wiki/Null-terminated_string
https://stackoverflow.com/questions/7648947/declaring-pascal-style-strings-in-c
https://stackoverflow.com/questions/4418708/whats-the-rationale-for-null-terminated-strings
https://en.m.wikipedia.org/wiki/String_(computer_science)#Length-prefixed
https://en.m.wikipedia.org/wiki/Rope_(data_structure)
https://queue.acm.org/detail.cfm?id=2010365
https://wiki.freepascal.org/Character_and_string_types
http://web.archive.org/web/20151125114234/http://www.codexterity.com/delphistrings.htm
https://wiki.freepascal.org/TStringList-TStrings_Tutorial
http://www.paulgraham.com/hundred.html

https://bobobobo.wordpress.com/2008/01/28/how-to-use-variable-argument-lists-va_list/

This one will be handy later :-)

Actually you can make the format more useful by extending the record backwards:

-4: uint_24: capacity, uint_8: flags

0: length (0-24b), uint_8 data[]

length: \0

This allows you to carry information about the capacity of the buffer in the record, for passing to str(n)* and snprintf routines. The flags could encode options like extend on demand, etc. which wrapper functions could use. Thus you still have compatibility with C library functions but can support enhanced behaviour.

Since this constitutes public disclosure, this extension cannot be patented from now on. 😉

yes, it is of course possible to extend backwards.

Now, I don't know how to tell a C compiler how to do it.

in C, I used to use a struct for Pascal-type strings, and it starts at address 0.

My idea is to use a 3rd bit of the pointer to flag the extra fields, which will take 4 more bytes like in you case.

There are various ways. One is to use an enclosing struct:

struct {

    uint_32 capflags;

   uint_8 data[];

}

Then mask the low 2 bits and subtract sizeof(uint_32) from the address you have to get to the capflags.

If you align to 8 bytes, you don't need to subtract the offset from the address :-)

Yes, but that might be a waste of memory and you would have to make sure that any heap allocation routines return that alignment.

@Ken Yap you can always re-align a pointer to a block you allocated.

Or even allocate a large block and make your own allocation system with the desired granularity :-)

Of course, but you have to overallocate in malloc then round up to the desired alignment. So 4 byte alignment may already be the default and you have to ensure 8 byte alignment with this method.

never mind : i'm about to settle for 16-bits alignment :-P

You can probably define a C++ class to handle these "ystrings" and to convert to and from C strings. Conversion to a C string is easy, just return the pointer. Conversion from a C string is more work, you have to allocate space and do a copy to ensure you have the alignment you want. It makes operations like ystrlen O(1) rather O(n) complexity.

Another consideration is whether you will normalise ystrings after an operation. For example all three represent the same string:

0 0 5 h e l l o \0

0 5 h e l l o \0

5 h e l l o \0

C++ is not for me... I'm having more fun with its bastard grandkid JavaScript, who rediscovers life's rules and hardships after turning 20 ;-)

"ystring" does not roll on my tongue but... nah :-P

Yes, conversion to C is easy. That's the point. It would ease communication with POSIX stuff (hopefully).

Conversion from C is less frequent and would occur in more deterministic situations. Most of the runtime cost (for my cases) is when strings are concatenated, when stuff is assembled, so the net gain should be positive. "reshifting" would occur only at the last moment when the whole batch is serialised/streamed/concatenated, normally only once.

You made a mistake with the degenerate cases : it's little endian ;-)

5 h e l l o \0

5 0 h e l l o \0

5 0 0 h e l l o \0

This really helps because the function only has to read the first 32-bits word and mask according to the pointer.

so normalisation is not critical : there is only one or two bytes of penalty for using a larger format, while enforcing a strict resize all the time is costly due to the constant reshifting.

If there is an overflow, you can avoid the cost of shifting by making a tree of strings.

But concatenation of C strings is already O(n) so can't get any better than that. Only if you have spare space behind one string can you reduce that to the length of one string. Anyway most of the work in s(n)printf is converting the data to characters so saving a bit of string manupulation won't make much difference to CPU work.

managing memory during multiple concatenations can be a P.I.T.A. and it happens a lot...

Remember : I am implementing a HTTP server, which has to manage quite a number of strings of various and variable sizes...

You can only do so much with snprintf() in this case : you can say what is too much but this is arbitrary... and you have to deal with the eventual error anyway.
If you concatenate with a tree first, you get the size of the whole string to allocate before serialising it. And you can process/manage the error before the serialisation happen.

@Ken Yap : this format actually can get better than that. It can concatenate two strings into one "non-ASCIIZ-compatible two-pointer" format "ystring" in O(1) time. You are right that creating an ASCIIZ string of length N by concatenation will inevitably take at least O(N) no matter how you do it. However, concatenating N separate strings of average length M with strcat() requires O( M*N^2 ) ( Schlemiel the Painter's Algorithm https://www.joelonsoftware.com/2001/12/11/back-to-basics/ ) but O( N + N*M ) by making a tree of two-pointer nodes, and flatting down to one long ASCIIZ string only once at the end.

Well, @Ken Yap  it seems I have settled on a flexible mix of features, look at the latest version :-)

I'm currently writing design decision docs, I'll post a summary here later.

I hope you will thoroughly audit your implementation for weaknesses because imagine what havoc an explotable bug in such a fundamental data structure shared library would cause if it's widely adopted. You could become famous for the wrong reasons. ☹

@Ken Yap  that's what regression tests and fuzzing are, right ?

That's only the start of it. If you look at CVEs even things like Perl's sort becoming quadratic on certain inputs was regarded as a weakness.

I like this. I may use it myself in the future.  Please do not patent! lol

There is no risk : a patent can't apply on a format. Only on methods.
I write everything under AGPLv3 (unless required by a client).
Many software use a prefixed format with size being 4 bytes, which is a waste  but keeps the code short and fast. I'm trying to find a compromise...

Tell us what you think :-)

I had occasion to use pascal-style strings just yesterday.  It wouldn't have helped in that particular case because all the data were small so I could get away with a fixed size of 8-bits for the length, but I like your adaptable solution for other cases where it might need to spill over to 16-bits or more occasionally, rather than bumping up all lengths to 16-bit just because a few happened to be long.
Vaguely it reminds me of how UTF8 achieves bisexuality with the ANSI world, but your use of the lower two bits of the pointer to encode the length of the length is particularly clever.
I was joking about patents, of course, however this is in fact a 'method'.

Feel free to use that trick :-)

If you only have 1 and 2 bytes for the size, you can simply test the LSB of the pointer and select the appropriate processing code. I am considering that "degraded mode" for 16-bits platforms.

I am thinking a lot about it, now, it's my new pet idea and a lot of things are flashing through my head, we'll see in the next days and weeks after the brightest ideas have percolated to the top...

Using the LSB to encode meta-informations is not new : I think some LISP and IA machines use this technique (for example, add a flag to indicate the type of a node in a linked list or tree) but the "smart" idea here is that the pointer serves 2 purposes at once ! It can indicate the format and still point to the start of the string ! It sounded so cool that I wondered why nobody did it before and I am still digesting a lot of documentation on the subject.

Yes I was thinking that a better analogy than UTF8 might be ARM Thumb instructions:  the LSB of the address indicates whether the target code (of a call or interrupt vector) is actually Thumb instructions.  Since instructions can never be on an odd address, they re-purposed that otherwise unused bit.  (I know this well from disassembling, lol)
Your encoding technique is still useful on 32-bit platforms.
It will be interesting to hear your thoughts about it's applicability to trees and linked lists when you get to that.

Yes, playing with pointers is a risky business...

I've been a CPU architecture geek for a long while and it is always tempting to use "some bits here and there" for "this and that"... And it often backfires.

Here it might be a sweet spot, we'll see. Anything is better than sprintf() ;-)