Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147642
| Subject | Re: One works, the other doesn't? |
|---|---|
| Newsgroups | comp.lang.c |
| References | <OHIvF.6838$u_3.620@fx29.iad> <qppdj2$52q$1@dont-email.me> <0EgwF.8082$kt1.6599@fx46.iad> <qpscqt$g9n$1@dont-email.me> |
| From | DFS <nospam@dfs.com> |
| Message-ID | <iKnwF.65564$P37.23863@fx33.iad> (permalink) |
| Organization | blocknews - www.blocknews.net |
| Date | 2019-11-05 18:35 -0500 |
On 11/5/2019 12:51 PM, James Kuyper wrote:
> On 11/5/19 10:34 AM, DFS wrote:
>> On 11/4/2019 9:45 AM, James Kuyper wrote:
>>> On 11/3/19 5:39 PM, DFS wrote:
> ...
>>>> Am I allocating memory incorrectly?
>>>
>>> Quite thoroughly. I'm not sure you did anything correct with regards to
>>> your use of dynamically allocated memory.
>>
>>> Also, there's no need for you to use dynamically allocated memory for
>>> this purpose:
>>>
>>> int cnt=0;
>>> for(i=0;i<arrsize;i++) {
>>> while (i<arrsize-1 && strcasecmp(randoms3[i],
>>> randoms3[i+1])==0)
>>> {i++}
>>>
>>> printf("%d %s ",cnt, randoms3[i]);
>>> cnt++;
>>> }
>>
>>
>> ? I never wrote that. ...
>
> I wrote nothing to suggest that you had written it.
>
>> ... You concocted it somehow. If you're just
>> showing it as an example, ...
>
> I was.
>
>> ... I agree there's no need for dyn alloc mem there.
>
> Which is why I preceded the example with a statement that dynamic
> allocation wasn't needed.
>
>> What I wrote was:
>>
>> printf("%d %s ",cnt,finalarr[cnt]);
>>
>> so I could see what was copied to finalarr after each loop iteration.
>
> But randoms3[i] IS what was copied to finalarr. The code you wrote
> provided no reason for the existence of finalarr.
Now I see where you were going. Since all I ever did was copy the
unique elements to finalarr then print them from finalarr, there was no
need for it to even exist. You're right.
My thinking was this:
- two initial arrays of the same size N/2
- combine them into a new array size N
- sort and dedupe and copy the unique elements into a final array of the
exact size N-dupes.
But rather than grow that last array as each element is added, you
pointed out it's better to allocate bigger chunks. Then realloc(arr,0)
will free extra-allocated memory.
> What it did with
> finalarr was completely incorrect, but in order to advise you on how it
> should be corrected, we need to know how finalarr was intended to be
> used. Your code below provides that context.
>
>>> It's possible that the full original context of this code provides a
>>> good reasons for dynamically allocating this memory. If so, let us know,
>>> and we can give you advice on how to do it properly (which will probably
>>> involve the use of realloc()).
>>
>> Thanks for your assessment James. Before you answered I tried realloc
>> in the larger program and it appears to work, in that it copies the
>> unique data to the finalarr (whether it's 10 elements or 1000000
>> elements), but the program fails and quits after the next to last line.
>>
>>
>> int cnt=0;
>> char **finalarr = malloc(sizeof(char*));
>> for(i=0;i<arrsize;i++) {
>> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
>> finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
>
> realloc() attempts to allocate the specified amount of space. If that
> attempt fails, it returns a null pointer. If that attempt succeeds, it
> then copies from the old allocation to the new one, for a number of
> bytes equal to the size of the smaller of the two allocations. As a
> optimization, it usually tries to allocate the new memory at the same
> starting location as the original allocation, if it can, which allows it
> to skip the expensive copying step - but the standard says nothing about
> this optimization.
>
> This leads to a couple of important points you need to keep in mind when
> using realloc().
>
> Like malloc(), realloc() can fail, in which case it returns a null
> pointer. If that happens, the previously allocated memory remains
> allocated. If you store the result of calling realloc() in the same
> place that you stored the only pointer you have to the original
> allocation, then if realloc() fails, you will never again be able to
> access the data you stored in that location, and you will never be able
> to free() it, leading to a memory leak. The right way to use realloc() is:
>
> void *tmp = realloc(finalarr, (cnt+1)*sizeof *finalarr);
> if(!tmp)
> {
> // Error handling
> } else {
> finalarr = tmp;
> }
https://www.thegeekstuff.com/2010/10/linux-error-codes/
Looking there, it seems ENOMEM (out of memory) is the only error that
would be returned by malloc() or realloc(). If so, would you typically
end the program, or would you try to free unused memory from elsewhere?
> The second point is that realloc() is a very expensive function to call.
> It starts out doing the same thing that malloc() does, searching through
> the heap for a block that is big enough (and preferably as small as
> possible), which is expensive in itself. On top of that, it also copies
> the data over from the previous allocation. Therefore, you should
> generally avoid calling it more often than necessary.
Once I fixed that format spec issue, the program ran fine with this call
to realloc() that was executed once per loop iteration:
finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
My goal was to size the final array to the exact size needed. But, as
you say above, it's 'very expensive' to call realloc. It doubled the
processing time vs my original (from 2 to 4 seconds, but still).
> A common strategy
> is to initially call malloc() to allocate significantly more than one
> object, and to only call realloc() when you reach the end of the current
> allocation and need to add more to it.
Using that strategy, I have this (seems to work, and very quickly):
int cnt=0, reallocated = 0;
char **finalarr = malloc(sizeof(char*) * (arrsize/2));
for(i=0;i<arrsize;i++) {
while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
finalarr[cnt] = randoms3[i];
cnt++;
if(cnt>=(arrsize/2) && reallocated==0) {
finalarr = realloc(finalarr, sizeof(char*) * (arrsize));
printf("reallocated at cnt = %d\n",cnt);
reallocated = 1;
}
}
realloc(finalarr, 0);
printf("%.4fs to remove %d dupes\n",elapsedtime(start),arrsize-cnt);
It mallocs finalarr to 1/2 the size of the source array, then when
finalarr gets full it reallocs the remaining half.
But it's getting clunky with the 'reallocated' flag. Got any other
methods to know when it's time to reallocate?
So far, 3 versions (array of 1M random elements of random size 8 to 16)
1. 2.4061s to remove 8 dupes
2. 4.8236s to remove 8 dupes
3. 0.1926s to remove 8 dupes
1 = count unique, then separate loop to copy to final array
2 = count and copy in same loop, malloc 1 entry up front then realloc()
1 element each loop
3 = count and copy in same loop, malloc 1/2 up front then realloc() 1/2
during the loop (your 'common strategy')
The last one is 12.6x as fast as the first (and 25x as fast as the
second). So that's nice. Good tip.
> When it is time to allocate more
> memory, increase the total size allocated by a fixed factor (2 is a
> popular value for that factor). As a result, the number of calls to
> realloc() is proportional to log(N), where N is the final value for the
> number of elements used. This will generally leave you with more memory
> allocated than is actually needed, but if that's a problem, you can
> realloc() back to that actual space needed at the end of the loop, which
> might release some of the excess memory.
I would like to free any unused memory right after this 'copy unique
items' operation.
Looks like realloc(finalarr,0) does it.
And that lets me continue to use finalarr afterwards, but then a call to
free(finalarr) at the end of the code throws an error. Which is good, I
think, because it means there is no longer any unused memory allocated
to finalarr, right?
Is there an easy way to measure the amt of memory freed by that command?
> Refinement 1: on many systems, allocating memory in blocks whose size is
> an integer multiple of some particular power of 2 is more efficient than
> allocating slightly more or slightly less than that amount. Which power
> of two is relevant varies from one system to another. On some systems,
> there's multiple different powers of 2 which have corresponding
> efficiency advantages. If your initial allocation is for a power of 2
> elements, and your growth factor is 2, you're virtually guaranteed to
> hit sizes that are particularly efficient.
When you say 'growth factor of 2' do you mean malloc N elements, then
continue to realloc 2N elements as needed?
To work with allocations of power of 2 I'll determine the closest power
of 2 that's greater than 1/2 the size of the source array, and use that
as a starting point.
Also, the number of dupes grows and shrinks inversely to the size of the
random strings. Running my program I see:
* randoms of size 2 to 4 will have a lot of dupes, even when run for
only 1000 elements.
* randoms of size 8 to 16 generate no dupes, even when run for 10M
elements.
> Refinement 2:
> I have vague memories of someone claiming to have seen a study
> suggesting that, at least under some common circumstances, the optimal
> growth factor is actually sqrt(2). I don't remember what those
> circumstances are.
> Using sqrt(2) directly would require floating point multiplications and
> conversions back to an integer. A better approach is to use the
> following: on even steps, set newsize = (oldsize*3)/2; on odd steps use
> newsize = (oldsize*4)/3. The average growth factor is exactly sqrt(2),
> but the individual expressions only use integer arithmetic.
>
> Refinement 3: on many systems, the malloc() family takes the space you
> requested, adds the size of a header, and then rounds up to the next
> multiple of a fixed block size. It allocates that much memory, writes
> the header at the beginning of the allocation, and returns a pointer
> just past the end of the header. Net result: it's the total size,
> including the header, that ideally should be an integer multiple of some
> particular power of 2. If the requested size is an efficient size, then
> the corresponding total size is virtually guaranteed to be a
> significantly inefficient size.
> Since the size of that header varies from one implementation to another,
> portable code has no way of dealing with this complication. Non-portable
> code can be designed to take into consideration the size of the header.
Those are interesting refinements. I'm going to work with Refinement #1
and see if I can get any significant speed increases.
>> finalarr[cnt] = randoms3[i];
>> printf("%d %s \n",cnt,finalarr[cnt]);
>> cnt++;
>> }
>> printf("%d here\n",cnt);
>> printf("%.4s remove %d dupes\n",elapsedtime(start),arrsize-cnt);
>
> You've already been informed about the problem with that format string.
Nice answer, James. Thanks for taking the time. I'm learning a lot
here on clc.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-03 17:39 -0500
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-04 00:20 +0000
Re: One works, the other doesn't? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-04 06:53 +0000
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-04 09:45 -0500
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 10:34 -0500
Re: One works, the other doesn't? mark.bluemel@gmail.com - 2019-11-05 07:45 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 10:53 -0500
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-05 08:04 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 11:29 -0500
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-05 23:24 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-05 23:06 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 12:31 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-05 23:43 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 12:54 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 01:35 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 15:16 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 11:11 +0000
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 01:59 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 11:35 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 08:57 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:24 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 22:59 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 14:37 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 00:58 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 02:08 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 15:43 +0100
Re: One works, the other doesn't? Robert Wessel <robertwessel2@yahoo.com> - 2019-11-07 16:15 -0600
Re: One works, the other doesn't? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-10 20:01 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-11 15:26 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-11 12:37 +0100
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:21 +1300
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 10:39 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:47 +1300
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 08:14 +1300
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 12:30 -0800
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 21:04 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 01:37 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 01:38 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-10 08:32 +1300
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 16:09 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-29 11:33 +0100
Re: One works, the other doesn't? Öö Tiib <ootiib@hot.ee> - 2019-11-30 14:20 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-12-01 12:15 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 10:07 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 10:58 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 10:05 +0100
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 09:52 +0100
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-06 00:56 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-06 01:00 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 11:32 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 23:11 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 23:22 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 01:04 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 01:13 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 10:22 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 11:51 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 15:58 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 16:34 +0000
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-07 12:40 -0500
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 17:57 +0000
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-07 21:14 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-08 09:45 +0000
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-08 09:56 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-08 19:47 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:14 +1300
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-08 19:10 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-09 12:24 +0000
Like an old married couple... (Was: One works, the other doesn't?) gazelle@shell.xmission.com (Kenny McCormack) - 2019-11-08 20:25 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 19:58 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 19:31 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 08:56 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 20:06 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 09:21 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 21:20 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 10:28 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 22:35 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:22 +1300
Re: One works, the other doesn't? jadill33@gmail.com - 2019-11-07 08:37 -0800
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 08:52 -0800
Re: One works, the other doesn't? jadill33@gmail.com - 2019-11-07 09:52 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 20:04 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 19:50 -0800
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 18:05 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-05 09:28 -0800
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 19:02 +0100
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-05 23:21 +0100
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-06 18:36 +0100
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-05 12:51 -0500
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 18:35 -0500
Re: One works, the other doesn't? Barry Schwarz <schwarzb@delq.com> - 2019-11-05 17:53 -0800
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-06 09:33 -0500
Re: One works, the other doesn't? Barry Schwarz <schwarzb@delq.com> - 2019-11-05 13:36 -0800
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-07 10:17 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-07 12:19 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-07 18:59 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-08 00:02 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-20 10:54 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-20 11:14 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-20 13:22 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 15:54 -0800
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-20 08:42 -0800
Re: One works, the other doesn't? Manfred <noname@add.invalid> - 2019-11-21 18:56 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-22 01:07 +0000
Re: One works, the other doesn't? Manfred <noname@add.invalid> - 2019-11-22 15:27 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 15:47 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-07 18:41 -0500
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 17:39 +0100
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 11:47 -0500
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 17:54 +0100
Re: One works, the other doesn't? luser droog <luser.droog@gmail.com> - 2019-11-05 09:00 -0800
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 21:02 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-09 02:09 -0500
csiph-web