Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > fully fast resizable arrays in c (c2)

Reply
Thread Tools

fully fast resizable arrays in c (c2)

 
 
fir
Guest
Posts: n/a
 
      03-18-2013
>
> (many codes in c would by much nice with that)
>


simple example on that

you need to read file from disk or net into an
array: you allocate some table then read bytes
into it, if file is bigger then your array you resize it wih some amount of bytes, read on,
and continue in loop till all is read into
array (or some exceptional limit reaced), then you can use this data and you do not waste
ram on to much big static buffer - finaly you
can resize it down to free ram

 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      03-18-2013
On 3/18/2013 1:55 PM, fir wrote:
> W dniu poniedziałek, 18 marca 2013 18:43:17 UTC+1 użytkownik Eric Sosman napisał:
>> [...]
>> Unix programmers have been doing this for years, using the
>> mmap() system call to reserve virtual addresses and relying on
>> the paging system to attach them to physical memory as needed.
>> I have my doubts about the wisdom of this approach (briefly: the
>> VM system knows less about your application's access patterns
>> than you do, or than you should), but a former colleague was a
>> great fan of the technique. It was a favorite topic for lunchtime
>> debates, when each of us would prove the other a complete idiot.

>
> IMO it is good for them if they do, IMO it is
> good - but it is somewhat unconvenient to do
> it with lov level api imo this should be build in c language addition as a 'resizable array' type
> easy to use as a fundamental part of language
> (many codes in c would by much nice with that)
> such thing they probably did not (I never heard of such extension to c at least)


Well, go ahead if you like -- it's your language, after all,
and not C that we're talking about. I'll point out, though, that
the mmap() technique is in fact *easier* to use than your proposal,
since it requires only one explicit action by the programmer, with
no "resize" operation at all.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
 
 
 
Anders Wegge Keller
Guest
Posts: n/a
 
      03-18-2013
Eric Sosman <(E-Mail Removed)> writes:

> I have my doubts about the wisdom of this approach (briefly: the
> VM system knows less about your application's access patterns
> than you do, or than you should)


On the other hand, the VM subsystem knows a whole lot more about the
available memory, and the peculiarities of the executing system, than
the programmer have time to figure out.

--
/Wegge

Leder efter redundant peering af dk.*,linux.debian.*
 
Reply With Quote
 
fir
Guest
Posts: n/a
 
      03-18-2013
W dniu poniedziałek, 18 marca 2013 19:18:02 UTC+1 użytkownik EricSosman napisał:
> On 3/18/2013 1:55 PM, fir wrote:
>
> > W dniu poniedziałek, 18 marca 2013 18:43:17 UTC+1 użytkownik Eric Sosman napisał:

>
> >> [...]

>
> >> Unix programmers have been doing this for years, using the

>
> >> mmap() system call to reserve virtual addresses and relying on

>
> >> the paging system to attach them to physical memory as needed.

>
> >> I have my doubts about the wisdom of this approach (briefly: the

>
> >> VM system knows less about your application's access patterns

>
> >> than you do, or than you should), but a former colleague was a

>
> >> great fan of the technique. It was a favorite topic for lunchtime

>
> >> debates, when each of us would prove the other a complete idiot.

>
> >

>
> > IMO it is good for them if they do, IMO it is

>
> > good - but it is somewhat unconvenient to do

>
> > it with lov level api imo this should be build in c language addition as a 'resizable array' type

>
> > easy to use as a fundamental part of language

>
> > (many codes in c would by much nice with that)

>
> > such thing they probably did not (I never heard of such extension to c at least)

>
>
>
> Well, go ahead if you like -- it's your language, after all,
>
> and not C that we're talking about. I'll point out, though, that
>


>

alrite but it would improve c so i post it here
as in theme of 'c improvements'


> the mmap() technique is in fact *easier* to use than your proposal,
>

as to mmap() i do not know what it is doing
but i guess it alocates logical and then
system binds physical pages on touch (?)


> since it requires only one explicit action by the programmer, with
>
> no "resize" operation at all.
>


these two 'operations' here - (1) giving (at compile time) a logical ram reserves to according
arrays, and (2) binding/unpinding phisical pages
on resize commands - are more 'suitable' here
(when just array with physical resize ability is needed), (but this mmap stuff is interesting
never heard more about that also my knowledge
about windows virtual memory api is not too good
so I am not sure if I just could write such c (c2)
compilers with such dynamic arrays supported,

(it would be good if i could, will work on that but it is still some time to go )




 
Reply With Quote
 
Michael Angelo Ravera
Guest
Posts: n/a
 
      03-18-2013
On Monday, March 18, 2013 2:28:39 AM UTC-7, fir wrote:
<FIR>
sorry for my weak english

It is somewhat suprising maybe, but my
recent thinking in this theme, brings to
me some notice, that on some platforms (like windows)
there is (would be) no problem with
full speed resizable arrays - c language
could support resizable arrays to
completion of normal noresizable arrays

it caould be just like this

resizable(50*1024*1024) char tab[1024];

or something like that with some better sytax
(where 50*1024*1024 is here a limit of max resize)

here, system should alloc tab[1024] and reserve
1024*1024*50 bytes of logical memory but just
bind 1024 bytes of physical memory at start

with some

resize tab[10*1024*1024];

or

resize tab[10];

then it could bind unbind physical ram to it

So it looks like that there is no problem
of getting lov lewel resizable and fully fast
primitive arrays in c on some system

(I am working on language codenamed c2 which
is c with improvements and i would wery much like
to get it here) (!)
</MAR>

It would be possible, if you tell the compiler in advance, for the compilerto allocate the array at some memory mapped address out of the normal allocation sequence and only clear the first so many units of memory. This would mean that you could probably write the memory beyond what was cleared andread it only at your own risk. You wouldn't have to resize it ever. If youwere to do a declaration something like:
<HYPOTHETICALQUOTE>
mapped char tab [1024];
</HYPOTHETICALQUOTE>

You could probably, subject to implementation limitations, execute a statement like:
<HYPOTHETICALQUOTE>
strcpy (& tab [36243688675309LL], "*** eye catcher ***");
</HYPOTHETICALQUOTE>
and have it work.

If the implementation is clever, it might not even have to write all of theintervening data spaces.





 
Reply With Quote
 
glen herrmannsfeldt
Guest
Posts: n/a
 
      03-18-2013
Keith Thompson <(E-Mail Removed)> wrote:
> fir <(E-Mail Removed)> writes:


(snip)
>> here, fortunately seem that it just could be done by malloking
>> additional storage (freeing some of it) at the end of array without
>> touching the contents of array


> That's possible only if the memory immediately after the end
> of the array happens to be available for allocation. realloc()
> already does this, but if it can't expand the array in place it
> will attempt to allocate new storage.


>> seem to me that it is just possible on some systems like windows, with
>> its virtual (logical/physical) memory system so i opt (propose) to do
>> that in some compiler of 'improved c' to use by programmers


> On a system without virtual memory, it's fairly obviously not
> possible in general to expand an array without either pre-allocating
> the maximum size or changing its base address, copying the old data
> into the newly allocated space (and invalidating any pointers into
> the original array).


> On a system with virtual memory, virtual addresses are still visible
> to the program. On a system with with a monolithic virtual address
> space (like most modern systems), you might be able to map additional
> physical memory onto the end of an existing array in virtual memory,
> but there's no guarantee that those addresses will be available.
> If I have an array whose starting and ending virtual addresses, when
> converted to uintptr_t, are 0x00001000 .. 0x00002000, I can't double
> its size if another object starts at virtual address 0x00002100.


Well, if you use 80386 (and later) segments then you could pretty
much do it. The hardware knows how to do it, but few OS do.
(Possibly OS/2 can still do it.)

The process-local segment selector limit is 8191 (no selector zero),
though, which can be limiting. Each can address 4GB. Considering
segment selectors, the 80386 has two (global and local) 45 bit
virtual address spaces, unfortunately with a 32 bit MMU in
between that and physical storage.

> But *maybe* the initial allocation could reserve a large range
> of virtual addresses without allocating physical memory for all
> those addresses. For example, you might request a thousand bytes,
> expandable to a million. The allocation call (not malloc()) could
> (attempt to) allocate a million virtual addresses, but map only
> the first thousand to physical memory. A later reallocation call
> (not realloc()) could then (attempt to) allocate addition physical
> memory and map it to the pre-reserved range of virtual addresses.


Not quite the same, but this reminds me of Linux style lazy allocation.
As I understand it, malloc() can allocate more VS than available backing
store. So, you can preallocate as big as you want, not worry about
reallocation, and use what you need.

> I think that would be usable only on a system where physical memory
> occupies only a small portion of the total virtual address space
> (e.g., not on a 32-bit system with exactly 4 gigabytes of RAM).
> We're still pretty far from filling 64-bit address spaces with
> physical RAM.


It might work. I am not so sure how the actual implementations
are right now. S/370 and VAX both have a two level virtual
storage, IBM calls segments and pages, VAX calls pagable page
tables. For the 64 bit z/Architecture, IBM designed in five
levels, but then allows one to use fewer levels for current
sized physical memory. You might use up too much memory
for tables for some sparce configurations.

> I have no idea how practical it would be to implement it, or
> whether it's already been done, or for that matter how useful it
> would really be.


Most of the time realloc() works well enough for me, but you can
only do realloc() at the end for one array at a time.
(Only one can be at the end.)

> Without this feature, the usual approach in C is to use realloc()
> and live with the fact that pointers can be invalidated. (In C++,
> the indexing operator can be overloaded in software to access
> non-contiguous array-like data structures; the same thing can be
> done in C without the syntactic sugar.)


-- glen
 
Reply With Quote
 
fir
Guest
Posts: n/a
 
      03-19-2013
W dniu poniedziałek, 18 marca 2013 10:28:39 UTC+1 użytkownik fir napisał:
>
> (I am working on language codenamed c2 which
> is c with improvements and i would wery much like
> to get it here) (!)


as to syntax probably

int tab[4000, (100000)] ;

// allloc 4000 ints physical ram
// but reserve logical space for
// 1000000 ints

this is good

then there is a need for command for resizing it
at runtime like "resize tab[20000];" or something
like that - it would be easy to use and quite
efficient in use i hope




 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      03-19-2013
fir wrote:
>
> So it looks like that there is no problem
> of getting lov lewel resizable and fully fast
> primitive arrays in c on some system
>
> (I am working on language codenamed c2 which
> is c with improvements and i would wery much like
> to get it here) (!)


It's called C++ and you want std::vector..

--
Ian Collins
 
Reply With Quote
 
Tiib
Guest
Posts: n/a
 
      03-19-2013
On Monday, 18 March 2013 20:18:02 UTC+2, Eric Sosman wrote:
> On 3/18/2013 1:55 PM, fir wrote:
> > W dniu poniedziałek, 18 marca 2013 18:43:17 UTC+1 użytkownik Eric Sosman napisał:
> >> [...]
> >> Unix programmers have been doing this for years, using the
> >> mmap() system call to reserve virtual addresses and relying on
> >> the paging system to attach them to physical memory as needed.
> >> I have my doubts about the wisdom of this approach (briefly: the
> >> VM system knows less about your application's access patterns
> >> than you do, or than you should), but a former colleague was a
> >> great fan of the technique. It was a favorite topic for lunchtime
> >> debates, when each of us would prove the other a complete idiot.

> >
> > IMO it is good for them if they do, IMO it is
> > good - but it is somewhat unconvenient to do
> > it with lov level api imo this should be build in c language addition
> > as a 'resizable array' type
> > easy to use as a fundamental part of language
> > (many codes in c would by much nice with that)
> > such thing they probably did not (I never heard of such extension to
> > c at least)

>
> Well, go ahead if you like -- it's your language, after all,
> and not C that we're talking about. I'll point out, though, that
> the mmap() technique is in fact *easier* to use than your proposal,
> since it requires only one explicit action by the programmer, with
> no "resize" operation at all.


There is portability issue (we all know with whom) mmap() has to be
replaced with MapViewOfFile() there; sbrk() with VirtualAlloc().

In C++ it is lot less an issue since the containers take optional
allocator arguments there. It would be very nice to have it in C.
 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      03-20-2013


"fir" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> W dniu poniedziałek, 18 marca 2013 10:28:39 UTC+1 użytkownik fir napisał:
>>
>> (I am working on language codenamed c2 which
>> is c with improvements and i would wery much like
>> to get it here) (!)

>
> as to syntax probably
>
> int tab[4000, (100000)] ;


> // allloc 4000 ints physical ram
> // but reserve logical space for
> // 1000000 ints
>
> this is good


Having to specify an upper limit is not good. If you're not sure what it
might be, then you might over-allocate and use up valuable virtual memory
space (if on 32-bits), or even waste page-table resources.

And suppose you don't know the likely upper limit until runtime?

> then there is a need for command for resizing it
> at runtime like "resize tab[20000];" or something
> like that - it would be easy to use and quite
> efficient in use i hope


That seems a clumsy way to increase the size of an array (reducing the size
is less common, so can work better with such an approach,, but even then,
reductions are commonly associated with deleting elements in the middle, so
'delete tab[i]' is probably more useful).

Suppose you had an array growing from 0 to 1000000 elements: you'd have to
write this:

int tab[0,(1000000)];

for (i=0; i<1000000; ++i) {
resize tab[i+1];
tab[i]=i*10;
}

It would be far tidier without that resize statement. And it might not
always be obvious when to apply it:

for (i=1; i<1000; ++i) {
j=random(1000000); // random index 0 to 999999;
resize tab [j+1]; // ????????
tab[j] = j*10;
}

How should this resize work? Perhaps tab is already of the same or bigger
size. Most of the calls can be redundant, if the array gets to a large size
early on, but you said you wanted it fast! Even with serial access, the
array allocation won't increase an element at a time, so most resizes will
do very little.

Don't forget also that you can have pointers to arrays, and array elements
(well unless you disallow pointers to resizable arrays):

int a[10];
int* p;

if (cond1) p=&a[i]; else p=&tab[i];

if (cond2) ++p; /* This might need a resize *if* p points to the
current end of tab. */
*p=56;


--
Bartc

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multidimensional arrays and arrays of arrays Philipp Java 21 01-20-2009 08:33 AM
Not fully comprehending arrays and dynamic memory. Mark Healey C Programming 4 04-16-2006 06:24 PM
Help me fast please! Cisco 3005 VPN, need help with fully mesh configuration Engan Cisco 0 11-10-2004 11:44 AM
Resizable columns on a web datagrid Thiago Almeida ASP .Net 0 10-14-2003 11:59 PM
Resizable Arrays dms C++ 4 08-29-2003 12:51 PM



Advertisments