The problem with size_t

"jacob navia" <> wrote in message
news:hb6qmn$p0t$...
>I am implementing the bitstring type in the container library, and
> obviously I store the number of bits in a size_t...
>
> Problem is, in 64 bit versions, size_t grows to 8 bytes, what
> is an absolute overkill for a number that in most cases will
> fit in 16 bits, or, at most 32.

Bitstrings are the ones most in need of a 64-bit count; if you have 4GB'
worth of bytes, that's 32G bits.

Otherwise your argument can be applied to any 64-bit C system and any
datatypes, that size_t is overkill for an array or string of 2 or 3 bytes.

If the implementation of bitstring is hidden, then it's already been
suggested that you could use a variable-length count, returning a size_t (of
whatever width) to a length request.

But, it sounds like you will already have to use a 64-bit pointer to the bit
data, and your minimum allocation for the bitstring is likely at least 16
bytes (128 bits), so 64-bits for a length won't make much difference.

(This is a general problem with 64-bits I think; everyone wants 64-bit data
and the ability to move stuff around 64-bits at a time, but fewer are
interested in addressing more than 4GB of data in each task. Being forced to
almost double the memory needs in some cases, will cancel much of the
advantage.)

--
Bartc

bartc

In article <hb6qmn$p0t$>, jacob navia <> wrote:
>
>Problem is, in 64 bit versions, size_t grows to 8 bytes, what
>is an absolute overkill for a number that in most cases will
>fit in 16 bits, or, at most 32.

Why not make your size_t (and your pointers) 40 bits instead? You can still
use 64-bit registers for them, just chop off the high 3 bytes when storing to
memory, and zero them when loading from memory. That makes a terabyte of
usable address space. A terabyte should be enough for anyone.

--
Alan Curry

Alan Curry

On Oct 15, 5:11*pm, jacob navia <ja...@nospam.org> wrote:
> robertwess...@yahoo.com a écrit :
> > Another option is that you change representations as the size grows
> > past a certain point. *If you do that, could you not just alter the
> > vtable pointer to go "native" for the changed implementation? *This
> > would require that enough space be allocated for the largest version
> > of the fixed part of the container (or allow a "small" base part to be
> > specified, which would not allow the container to grow past a certain
> > point).
>
> I did not fully understand the above paragraph. Maybe you can expand?
> what would it mean to "go native" ?


I simply meant that you could change the type of container as its
contents grows. For example, when you hit the limit of a
SmallBitString container, convert the representation to a
LargeBitString container, and then change the vtable pointer. This
eliminates the need to start each routine in a more generic BitString
container with a switch statement based on the type. You'd have to be
careful about the size of the base object (it would effectively be a
union of the various types).

robertwessel2@yahoo.com

Stephen Sprunk wrote:

> If the user has a 64-bit system, it is extremely unlikely that saving
> four bytes of memory will matter.

It isn't just 4 bytes of memory. If you happen to use Jacob's bitstring on a data structure then it means an
extra 4 bytes for each node. As the data structure grows then, depending of the use you give it, you will
feel those extra 4 bytes being used up, specially if you target devices with limited memory.


Rui Maciel

Rui Maciel

"Richard Heathfield" <> wrote in message
news:...
> In <hb8pfe$6c8$>, Alan Curry wrote:
>
> <snip>
>
>> Why not make your size_t (and your pointers) 40 bits instead? You
>> can still use 64-bit registers for them, just chop off the high 3
>> bytes when storing to memory, and zero them when loading from
>> memory. That makes a terabyte of usable address space. A terabyte
>> should be enough for anyone.
>
> It may not be enough for the Meteorological Office. In early 2007,
> their database contained 1,400,000,000,000,000 bytes of information,
> and was growing at the rate of 1.4 Terabytes per day. It is not
> beyond the bounds of possibility that they could find 1 Terabyte of
> random access memory to be insufficient for their processing needs.

Why would it be necessary to have this data in the address space of a single
task? And why inflict the address size on the 99% of tasks that don't need
it?

But if we're going to memory map everything then let's go straight to
128-bits then the entire internet can potentially be in a program's address
space at once.

--
Bartc

bartc

Dik T. Winter wrote:

> Noob wrote:
>
>> jacob navia wrote:
>>
>>> [...] size_t grows to 8 bytes, what is an absolute overkill [...]
>>
>> <OT grammar nit>
>> In this context, one would write "which" not "what".
>> (English native speakers: is my statement correct?)
>> I've seen several francophone posters make this mistake.
>> Is this grammatical rule incorrectly taught in school, perhaps?
>> </OT>
>
> In French (as in Dutch) "which" translates in this position to a word that
> is also a translation of "what".

I disagree. In this context, "which" translates to "ce qui".

"size_t passe à 8 octets, *ce qui* est absolument excessif"

It is in a different context that "which" and "what" may translate to
the same word : "quel", as in

Which movie would you like to see?
What movie would you like to see?
=> "Quel film voudrais-tu voir ?"

Question to native speakers:
What is the nuance between "which" and "what" in the two questions?
*Which* movie would you like to see?
*What* movie would you like to see?

Both seem grammatical.
"which" seems to imply that a decision among several choices must be
made, whereas "what" seems to be more vague, in the sense that there
might not be any movies to see.

Regards.

Noob

Rui Maciel wrote:

> Stephen Sprunk wrote:
>
>> If the user has a 64-bit system, it is extremely unlikely that
>> saving four bytes of memory will matter.
>
> It isn't just 4 bytes of memory. If you happen to use Jacob's
> bitstring on a data structure then it means an extra 4 bytes for each
> node. As the data structure grows then, depending of the use you give
> it, you will feel those extra 4 bytes being used up, specially if you
> target devices with limited memory.

How common are 64-bit systems in "devices with limited memory" today?

Do you expect this number to grow significantly?

Noob

On 16 Oct, 11:37, Noob <r...@127.0.0.1> wrote:
> How common are 64-bit systems in "devices with limited memory" today?
>
> Do you expect this number to grow significantly?

Interesting point.

I don't know, but considering the number of small devices with limited
memory using POSIX based OS interface systems (e.g. Linux), and the
date issue in 2038, do you think these would soon upgrade to 64 bit
OSs and therefore move to 64bit CPUs?

I don't really know the embedded market for date based applications so
it is a genuine question.

fnegroni

In article <hb9hps$vdp$>, Noob <root@127.0.0.1> wrote:

> Dik T. Winter wrote:
>
> > Noob wrote:
> >
> >> jacob navia wrote:
> >>
> >>> [...] size_t grows to 8 bytes, what is an absolute overkill [...]
> >>
> >> <OT grammar nit>
> >> In this context, one would write "which" not "what".
> >> (English native speakers: is my statement correct?)
> >> I've seen several francophone posters make this mistake.
> >> Is this grammatical rule incorrectly taught in school, perhaps?
> >> </OT>

Using "what" in the manner above is grammatically incorrect and
immediately marks out the user as a non-native English speaker. "Which"
is correct here.

> > In French (as in Dutch) "which" translates in this position to a word that
> > is also a translation of "what".
>
> I disagree. In this context, "which" translates to "ce qui".
>
> "size_t passe à 8 octets, *ce qui* est absolument excessif"
>
> It is in a different context that "which" and "what" may translate to
> the same word : "quel", as in
>
> Which movie would you like to see?
> What movie would you like to see?
> => "Quel film voudrais-tu voir ?"
>
> Question to native speakers:
> What is the nuance between "which" and "what" in the two questions?
> *Which* movie would you like to see?

This is grammatically correct.

> *What* movie would you like to see?

This is more of a slang usage. Accepted as a synonym perhaps, but still
slang. It might also be short for:

What type of movie would you like to see?

which is in any case a different question.

PS I take it that you finally got rid of that twirp sp***za?
Congratulations, if so.

--
Tim

"That excessive bail ought not to be required, nor excessive fines imposed,
nor cruel and unusual punishments inflicted" -- Bill of Rights 1689

Tim Streater

Noob <root@127.0.0.1> writes:
[...]
> How common are 64-bit systems in "devices with limited memory" today?

All 64-bit systems have limited memory. Typically the limit is
fairly large. (And 640 gigabytes should be enough for anybody.)

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson