- std::vector<>::capacity()-growth - 5 Updates
- The key basis of the halting problem proofs - 11 Updates
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 16 06:31PM +0100 Some time I wrote a class called gvector<> which derived from vector<> and which grows the capacity of the vector by a constant value or a constant factor, whichever is greater, usually startoing at the con- stant value and then beeing overtaken by the constant factor at a certain size when the latter results in a larger capacity than the constant offset. Today someone in another forum told me, that some vector<>-impmemen- tations grow the capacity in powers of two. I couldn't believe that because it appeared to me as too much bloat. So I wrote a littel pro- gram to test this: #include <iostream> #include <vector> using namespace std; int main() { vector<size_t> vec; size_t lc = vec.capacity(); for( size_t i = 1000000; i; --i ) { vec.emplace_back( i ); if( lc != vec.capacity() ) lc = vec.capacity(), cout << lc << endl; } } This are the results of the current MSVC-compiler: 1 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066 1599 2398 3597 5395 8092 12138 18207 27310 40965 61447 92170 138255 207382 311073 466609 699913 1049869 I don't know which arithmetic pattern this growth follows, but it is obviously not linear. Here are the results of the libstdc++: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 So libstdc++ in fact grows the vector in powers of two. That's not what I expected since I so far assumed that growing the capacity efficiently is the duty of the programmer and growing the vector with such hops is really bloat for me. |
| Bo Persson <bo@bo-persson.se>: Mar 16 07:08PM +0100 On 2021-03-16 at 18:31, Bonita Montero wrote: > I expected since I so far assumed that growing the capacity efficiently > is the duty of the programmer and growing the vector with such hops is > really bloat for me. Here "efficiently" can mean either using less time or using less memory. Obviously libstdc++ grows in larger chunks (capacity x 2), which results in fewer reallocations. MSVC instead chose to grow by a factor of 1.5, which possibly results in more allocations, but uses less memory. One advantage of the 1.5 growth is that it can possibly resuse the space deallocated previously, while with a factor 2.0 the previous space is always *just* too small to be resused (1+2+4+8 < 16, 1+2+4+8+16 < 32, and so on). For more info see https://stackoverflow.com/questions/5232198/about-vectors-growth Bo Persson |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 16 07:41PM +0100 And is emplace_back() also required to satisify this constant time requirement ? Strongly spoken this a bit different than push_back(). And has std::string also such an exponential growth behaviour ? |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 16 07:47PM +0100 > And is emplace_back() also required to satisify this constant time > requirement ? Strongly spoken this a bit different than push_back(). > And has std::string also such an exponential growth behaviour ? They have - I've checked it at en.cppreference.com. |
| Marcel Mueller <news.5.maazl@spamgourmet.org>: Mar 16 09:40PM +0100 Am 16.03.21 um 19:08 schrieb Bo Persson: > deallocated previously, while with a factor 2.0 the previous space is > always *just* too small to be resused (1+2+4+8 < 16, 1+2+4+8+16 < 32, > and so on). In theory yes. In practice this only applies if no other allocation has been don in between. Otherwise it won't work because of fragmentation of virtual address space. A sufficiently sophisticated allocator can deal with such situations. It uses different pools depending on the allocation size. This can significantly reduce memory and address space fragmentation. However, std::vector is not a good choice for very large data, not even when the size is known before and no reallocation is required. It is more efficient to introduce some fragmentation into large data. This significantly simplifies memory management. I made very good experience with Btree structures with a fixed node size of 127. Well designed they can operate with only a few bits overhead per entry. Although they are O(log(n)) in many operations the base of 127 requires only 5 levels to store 2^32 Elements which is likely already an out of memory condition. So a Btree based structure is in practice almost constant time. Unfortunately there is still no Btree in the standard library. And if this changes at some time it will be most likely not that efficient. Marcel |
| olcott <NoOne@NoWhere.com>: Mar 16 08:30AM -0500 On 3/16/2021 6:29 AM, Richard Damon wrote: > I would say that MANY have been able to logically show many errors in > your basic reasoning. It is YOU who doesn't seem to be willing to accept > the Truth. I unified the key basis of all three proofs see the YELLOW HIGHLIGHTED portions of these two textbook proofs: http://www.liarparadox.org/sipser_165.pdf http://www.liarparadox.org/kozen_233.pdf into this simple C function that expresses this basis. void H_Hat(u32 P) { u32 Input_Would_Halt = Halts(P, P); if (Input_Would_Halt) HERE: goto HERE; } int main() { u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat); Output("Input_Would_Halt = ", Input_Would_Halt); } No one can show that this does not accurately represent the key basis of the proofs. The best that they can do is show that they do not understand what the key basis is. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 16 03:31PM +0100 STOP POSTING OFF-TOPIC-STUFF !!! |
| olcott <NoOne@NoWhere.com>: Mar 16 10:02AM -0500 On 3/16/2021 9:31 AM, Bonita Montero wrote: > STOP POSTING OFF-TOPIC-STUFF !!! It is not off-topic. It is directly related to the algorithm analysis of the machine language translation of a C program. I only cross-post key breakthroughs most of my posts are to comp.theory -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| Nikolaj Lazic <nlazicBEZ_OVOGA@mudrac.ffzg.hr>: Mar 16 03:13PM >> STOP POSTING OFF-TOPIC-STUFF !!! > It is not off-topic. It is directly related to the algorithm analysis of > the machine language translation of a C program. This is C++... Could you, please, stop? > I only cross-post key breakthroughs most of my posts are to comp.theory Please, please, please... stop. |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 16 04:23PM +0100 > It is not off-topic. It is directly related to the algorithm analysis of > the machine language translation of a C program. You're not discussing C-specific issues. What you disuss could be related to almost any language. > I only cross-post key breakthroughs most of my posts are to comp.theory Don't post in comp.lang.c(++) at all ! |
| olcott <NoOne@NoWhere.com>: Mar 16 10:44AM -0500 On 3/16/2021 10:23 AM, Bonita Montero wrote: > What you disuss could be related to almost any language. >> I only cross-post key breakthroughs most of my posts are to comp.theory > Don't post in comp.lang.c(++) at all ! The x86utm operating system is written in c++ -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 16 04:48PM +0100 >> Don't post in comp.lang.c(++) at all ! > The x86utm operating system is written in c++ That's not sufficient to post here. Post only C++-issues to comp.lang.c++. |
| Keith Thompson <Keith.S.Thompson+u@gmail.com>: Mar 16 09:13AM -0700 > Could you, please, stop? >> I only cross-post key breakthroughs most of my posts are to comp.theory > Please, please, please... stop. olcott will not stop cross-posting. He's been asked to do so many times. I've configured my newsreader so I never see anything he posts to comp.lang.c or to comp.lang.c++ -- which means I only see replies like yours. If you want to complain to him, please post only to comp.theory (which, last time I checked, is dominated by his posts anyway). -- Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com Working, but not speaking, for Philips Healthcare void Void(void) { Void(); } /* The recursive call of the void */ |
| olcott <NoOne@NoWhere.com>: Mar 16 11:37AM -0500 On 3/16/2021 11:13 AM, Keith Thompson wrote: > like yours. If you want to complain to him, please post only > to comp.theory (which, last time I checked, is dominated by his > posts anyway). When I stopped posting for 42 days no one else posted anything at all. I will greatly reduce by cross-posting to comp.lang.c and comp.lang.c++. If I could otherwise get my work peer reviewed I would have never needed to cross-post at all. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 16 06:20PM +0100 > I will greatly reduce by cross-posting to comp.lang.c and comp.lang.c++. Don't post here at all if you don't relate to C++-issues. Discussing computational problems which could be related to any language isn't sufficient to post here. |
| Nikolaj Lazic <nlazicBEZ_OVOGA@mudrac.ffzg.hr>: Mar 16 05:41PM > like yours. If you want to complain to him, please post only > to comp.theory (which, last time I checked, is dominated by his > posts anyway). Thank you... I know that I can use kill file... But than I will not see when Peter Olcott (God himself) finally desides to halt. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment