Ludovic 'Archivist'
(assuming global variables do not exist or are advertised to the GC)
Ludovic 'Archivist'
I will put that one in my beginner's exercises list...
● Igor
If you are curious @igorcmelo I suggest you try to implement a tiny garbage collector in C to learn how these things work. It is easier than it seems to implement a mark-and-sweep for single threaded programs
when you say implement a garbage collector, you mean to implement it to collect C garbage, or just like a conceptual garbage collector?
mj12
Well, not exactly Go, may "stop the world" to perform a garbage collection, this will halt all threads, do a parallel mark and sweep, before resuming execution. It will however detect any "loop" of derelict memory.
shared_ptr will not be able to easily collect a loop of derelict memory (as every member of a cyclic graph may always have at least 1 edge pointed at them) but it will also not stop the world or affect execution of other threads significantly (edge cases may exist)
> Well, not exactly Go, may "stop the world" to perform a garbage collection, this will halt all threads, do a parallel mark and sweep, before resuming execution.
Go implements generational GC, not refcounting, never did i state that it did. I was referring to the point about hidden control flow detailed below.
> but it will also not stop the world or affect execution of other threads significantly (edge cases may exist)
Wrong, this is entirely dependant on the Implementation of malloc/free of the crt you're using. I'd say anytime hidden control flow happens (such as freeing of objects managed by shared_ptr) it "stops the world" you're interacting with.
mj12
> Well, not exactly Go, may "stop the world" to perform a garbage collection, this will halt all threads, do a parallel mark and sweep, before resuming execution.
Go implements generational GC, not refcounting, never did i state that it did. I was referring to the point about hidden control flow detailed below.
> but it will also not stop the world or affect execution of other threads significantly (edge cases may exist)
Wrong, this is entirely dependant on the Implementation of malloc/free of the crt you're using. I'd say anytime hidden control flow happens (such as freeing of objects managed by shared_ptr) it "stops the world" you're interacting with.
Well, scratch the part about go implementing generational GC, i got confused there; see https://tip.golang.org/doc/gc-guide for more information
Anonymous
> Well, not exactly Go, may "stop the world" to perform a garbage collection, this will halt all threads, do a parallel mark and sweep, before resuming execution.
Go implements generational GC, not refcounting, never did i state that it did. I was referring to the point about hidden control flow detailed below.
> but it will also not stop the world or affect execution of other threads significantly (edge cases may exist)
Wrong, this is entirely dependant on the Implementation of malloc/free of the crt you're using. I'd say anytime hidden control flow happens (such as freeing of objects managed by shared_ptr) it "stops the world" you're interacting with.
Can you show me a C runtime where malloc/free add signinficant costs to your running program as compared to a stop the world GC algorithm or even the best case concurrent GC executions - GC implementations that pause just running threads when tracing through root objects on the current execution stack?
mj12
Can you show me a C runtime where malloc/free add signinficant costs to your running program as compared to a stop the world GC algorithm or even the best case concurrent GC executions - GC implementations that pause just running threads when tracing through root objects on the current execution stack?
If your memory is managed by malloc/free (especially in cases where it's unnecesarry), malloc/free typically have to lock in order to stay threadsafe. So in a scenario where 2 threads run code in a loop that allocates -> does some operation -> free's, you're spending a lot of time waiting for the other thread to finish in malloc/free
Anonymous
If your memory is managed by malloc/free (especially in cases where it's unnecesarry), malloc/free typically have to lock in order to stay threadsafe. So in a scenario where 2 threads run code in a loop that allocates -> does some operation -> free's, you're spending a lot of time waiting for the other thread to finish in malloc/free
Why does there have to be a lock? Malloc and Free typically work on a linked list data structure and such a linked list could be implemented in a lock free or even a wait free manner with pushing (allocations) happening at one end and popping (freeing) happening somewhere else. Even if we were to assume that a particular implementation were to use a lock, this would again be not a single lock maintaining the whole data structure but granular locks maintaining different nodes following a hand over hand locking policy (and careful deadlock avoidance mechanisms). This is true for GCC's implementation that I have seen.
Assuming the worst case that you shared where a single lock is used to maintain the entire data structure (I am pretty sure no implementation does this though), the performance would still not be as bad as compared to a tracing GC which pauses the whole program.
mj12
Why does there have to be a lock? Malloc and Free typically work on a linked list data structure and such a linked list could be implemented in a lock free or even a wait free manner with pushing (allocations) happening at one end and popping (freeing) happening somewhere else. Even if we were to assume that a particular implementation were to use a lock, this would again be not a single lock maintaining the whole data structure but granular locks maintaining different nodes following a hand over hand locking policy (and careful deadlock avoidance mechanisms). This is true for GCC's implementation that I have seen.
Assuming the worst case that you shared where a single lock is used to maintain the entire data structure (I am pretty sure no implementation does this though), the performance would still not be as bad as compared to a tracing GC which pauses the whole program.
> This is true for GCC's implementation that I have seen.
I haven't looked at glibc's implementation in particular, but i know that musl's does make use of locks quite a bit. Do you have anything you could link that i could read upon on how glibc avoids locks there (preferably documentation or something alike)?
> the performance would still not be as bad as compared to a tracing GC which pauses the whole program.
Do you have any benchmarks to back that claim up? I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.
In more or less rare edge cases the GC might beat malloc/free, simply because it doesn't have to deal with managing memory each time you exit a scope.
Ludovic 'Archivist'
> Well, not exactly Go, may "stop the world" to perform a garbage collection, this will halt all threads, do a parallel mark and sweep, before resuming execution.
Go implements generational GC, not refcounting, never did i state that it did. I was referring to the point about hidden control flow detailed below.
> but it will also not stop the world or affect execution of other threads significantly (edge cases may exist)
Wrong, this is entirely dependant on the Implementation of malloc/free of the crt you're using. I'd say anytime hidden control flow happens (such as freeing of objects managed by shared_ptr) it "stops the world" you're interacting with.
Even if there was a lock, that lock would at most prevent interactions with the allocator. That lock would not stop all code execution in threads, it would not be locking for the time of a long mark-and-sweep, and in most cases that lock would not exist at all because modern allocator generally support parallel allocations and deallocations of memory if both happened in the same thread
mj12
You just repeated what i said.
> I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.
Ludovic 'Archivist'
> This is true for GCC's implementation that I have seen.
I haven't looked at glibc's implementation in particular, but i know that musl's does make use of locks quite a bit. Do you have anything you could link that i could read upon on how glibc avoids locks there (preferably documentation or something alike)?
> the performance would still not be as bad as compared to a tracing GC which pauses the whole program.
Do you have any benchmarks to back that claim up? I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.
In more or less rare edge cases the GC might beat malloc/free, simply because it doesn't have to deal with managing memory each time you exit a scope.
Stop the world GC introduces jitter that may make it entirely unsuitable to use. Most of my personal use cases would literally break because of the random jitter of the GC
Ludovic 'Archivist'
> I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.
A stop the world on >64GB of application memory take around 16ms on a 4 cores / 8 threads CPU
Ludovic 'Archivist'
> I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.
Mark-and-sweep is pretty costly. When a full garbage collection happen, the cost of it is quadratic with total application memory. This means that on a system with between 256GB and 1TB of application memory, your GC may entirely go beyond the timeout of certain low latency operations
mj12
Mark-and-sweep is pretty costly. When a full garbage collection happen, the cost of it is quadratic with total application memory. This means that on a system with between 256GB and 1TB of application memory, your GC may entirely go beyond the timeout of certain low latency operations
Yea well, using certain types of GC in cases where real-time responses are necessary isn't the best idea. But I really wonder what the actual performance impacts here would be, in terms of how much (total) time you're spending managing memory manually, vs the amount of time the garbage collector takes.
mj12
Yea well, using certain types of GC in cases where real-time responses are necessary isn't the best idea. But I really wonder what the actual performance impacts here would be, in terms of how much (total) time you're spending managing memory manually, vs the amount of time the garbage collector takes.
In general i do think copying GC's get way too less credit for how good they *can* perform in some cases.
Ludovic 'Archivist'
Yea well, using certain types of GC in cases where real-time responses are necessary isn't the best idea. But I really wonder what the actual performance impacts here would be, in terms of how much (total) time you're spending managing memory manually, vs the amount of time the garbage collector takes.
It is significant enough for Go to be around 1.5 times slower on average than C++. It is not THAT slower and generally the fact that you don't do memory cleanup would have been considered simpler code before C++14
Anonymous
> This is true for GCC's implementation that I have seen.
I haven't looked at glibc's implementation in particular, but i know that musl's does make use of locks quite a bit. Do you have anything you could link that i could read upon on how glibc avoids locks there (preferably documentation or something alike)?
> the performance would still not be as bad as compared to a tracing GC which pauses the whole program.
Do you have any benchmarks to back that claim up? I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.
In more or less rare edge cases the GC might beat malloc/free, simply because it doesn't have to deal with managing memory each time you exit a scope.
I dont have any documentation but here is the code:
https://elixir.bootlin.com/glibc/glibc-2.36/source/malloc/malloc.c#L1824
That is the state that is internally used by malloc and free. There is a mutex per node and it is a linked list. There is no lock avoidance. There is a lock in glibc's implementation. But the lock is not a course grained lock and is a fine grained lock (a lock per individual malloc_state node). The reason why this is more efficient is because if there is a thread doing free (somewhere other than the the end of the linked list) while another thread is doing allocations, they both can happen at the same time. They dont have to wait for each other.
With a wait-free or a lock-free linked list, this would ensure that no thread has to wait for the other (provided there is hardware support) and all threads will be able to make progress.
>>>In more or less rare edge cases the GC might beat malloc/free, simply because it doesn't have to deal with managing memory each time you exit a scope.<<<<
Why do malloc or free have to deal with scopes? I don't understand what you are tring to say here.
>>>Do you have any benchmarks to back that claim up? I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.<<<
I dont have any benchmarks to show you but the fact that Hans Boehm and Sarita Adve tried (two of the best in the field) tried a Garbage Collection implementation in C++ and then gave it up because it was way slower than what they had hoped for and withdrew their paper proposing one (they didnt even wait to see if someone could come up with a better implementation) suggests that GCs would not help much with C/C++.
And yes I agree that effective performance will be affected only by the number of operations that happen in-between your memory allocations. But I would presume that for many programs the memory allocations on the heap would happen far less often as compared to other code running between them. So the chances of two threads happening to be stalled by a locking implementation of malloc/free would be a rare coincidence as compared to a tracing GC which by its nature pauses the whole program.
Ludovic 'Archivist'
Also, garbage collection makes cycle collection simpler as refcounting will have trouble with that
Ludovic 'Archivist'
when you say implement a garbage collector, you mean to implement it to collect C garbage, or just like a conceptual garbage collector?
Yes, I meant a garbage collector in C to collect C garbage
Ludovic 'Archivist'
Also, garbage collection makes cycle collection simpler as refcounting will have trouble with that
Another benefit of GC is, in languages with double indirection like C#, rezoning: moving the object to a better location in the heap during the stop-the-world. That is something with real performance benefits
Ludovic 'Archivist'
Rezoning may, in certain cases, make C# code faster than similarly optimized C++ or C
Anonymous
Another benefit of GC is, in languages with double indirection like C#, rezoning: moving the object to a better location in the heap during the stop-the-world. That is something with real performance benefits
Most generational GCs do something similar. However rezoning could be to done to ensure less defragmentation (generational GCs don,t avoid this though)
mj12
I dont have any documentation but here is the code:
https://elixir.bootlin.com/glibc/glibc-2.36/source/malloc/malloc.c#L1824
That is the state that is internally used by malloc and free. There is a mutex per node and it is a linked list. There is no lock avoidance. There is a lock in glibc's implementation. But the lock is not a course grained lock and is a fine grained lock (a lock per individual malloc_state node). The reason why this is more efficient is because if there is a thread doing free (somewhere other than the the end of the linked list) while another thread is doing allocations, they both can happen at the same time. They dont have to wait for each other.
With a wait-free or a lock-free linked list, this would ensure that no thread has to wait for the other (provided there is hardware support) and all threads will be able to make progress.
>>>In more or less rare edge cases the GC might beat malloc/free, simply because it doesn't have to deal with managing memory each time you exit a scope.<<<<
Why do malloc or free have to deal with scopes? I don't understand what you are tring to say here.
>>>Do you have any benchmarks to back that claim up? I'd say the "effective performance" (by that i mean how many of >your< operations actually get executed in a fixed time) depends a lot on the amount of work you're doing between managing memory.<<<
I dont have any benchmarks to show you but the fact that Hans Boehm and Sarita Adve tried (two of the best in the field) tried a Garbage Collection implementation in C++ and then gave it up because it was way slower than what they had hoped for and withdrew their paper proposing one (they didnt even wait to see if someone could come up with a better implementation) suggests that GCs would not help much with C/C++.
And yes I agree that effective performance will be affected only by the number of operations that happen in-between your memory allocations. But I would presume that for many programs the memory allocations on the heap would happen far less often as compared to other code running between them. So the chances of two threads happening to be stalled by a locking implementation of malloc/free would be a rare coincidence as compared to a tracing GC which by its nature pauses the whole program.
Oh, Thanks a lot for the explanation, that makes it a lot clearer
> Why do malloc or free have to deal with scopes?
Oh, my bad, the original discussion was referring to std::shared_ptr (which to my knowledge tracks the refcount via RAII, so scope enter/exit to some extent)
> and withdrew their paper proposing one
Are you referring to the garbage collection that tracks references via reachability detection? I think there's far more & potentially worse problems than *just* performance with those. Ultimately, i don't see a reason why garbage collection would be a good idea as a language feature in c++, as it pretty much gives you all the tools you need to solve the problems that GC fixes yourself.
Ajii
Anyone have any suggestion books or PDFs for beginners
Anonymous
Oh, Thanks a lot for the explanation, that makes it a lot clearer
> Why do malloc or free have to deal with scopes?
Oh, my bad, the original discussion was referring to std::shared_ptr (which to my knowledge tracks the refcount via RAII, so scope enter/exit to some extent)
> and withdrew their paper proposing one
Are you referring to the garbage collection that tracks references via reachability detection? I think there's far more & potentially worse problems than *just* performance with those. Ultimately, i don't see a reason why garbage collection would be a good idea as a language feature in c++, as it pretty much gives you all the tools you need to solve the problems that GC fixes yourself.
>>>Are you referring to the garbage collection that tracks references via reachability detection?<<<
I am referring to this implementation here : https://github.com/ivmai/bdwgc/
It provides an incremental and generational Garbage collector (similar to the one used in Java) for C++.
Many garbage collectors in use base their decisions on reachability from root nodes (global and locals on the execution stack). So not sure why you think they are bad when Go, C# and Java garbage collectors do so too.
Since most of the system development languages being developed now are moving towards a garbage collector, efforts were made to do so for C/C++ as well. The question was not whether C++ shouldnt have a garbage collector or not. The priority was to standardize memory allocation/deallocation algorithms giving implementations certain flexibility rather than keeping it entirely out of the purview of the standard as it is today. This is similar to C++ standards lacking a thread-aware memory model earlier but many programs were still using pthreads/win threads to write concurrent code in C++ on many platforms (with the run time library ensuring exception propagation and similar things across threads) despite the standard not talking about it.
Kinzy
what is the difference between fgets and gets? not in the syntax but in the function of it...
Anonymous
what is the difference between fgets and gets? not in the syntax but in the function of it...
https://lmddgtfy.net/?q=fgets%20vs%20gets
Talula
what is the difference between fgets and gets? not in the syntax but in the function of it...
"Even though both the functions, gets() and fgets() can be used for reading string inputs. The biggest difference between the two is the fact that the latter allows the user to specify the buffer size. Hence it is highly recommended over the gets() function." - Google.
Kinzy
thank you so much for your help
Michel
Is anything between #ifdef X #endif ignored if X is not met?
Serkan
Is anything between #ifdef X #endif ignored if X is not met?
As far as I know we use like this pattern
#ifndef X_HEADER
#define X_HEADER
.... Definitions
#endif
20BCS5685_AnishaKumari
can someone explain me how to take input for pair of vector inside a vector element, vector<vector<pair<int,int>>> v;
Michel
As far as I know we use like this pattern
#ifndef X_HEADER
#define X_HEADER
.... Definitions
#endif
That's one use case, I don't want to define anything, you can do
#ifdef X
//Some code
#else
//Other code
#endif
And pass -DX to the compiler during build for "Some code" and omit for "other code"
Serkan
Michel
Is anything between #ifdef X #endif ignored if X is not met?
Basically I want to wrap the host device options of CUDA inside #ifdefs so that my headers work for c++ and nvcc at the same time, is that a good idea?
Shahar
Can you recommend on good resources for clean C code? Best practices/clean code/design?
Michel
Search for "Google coding guidelines"
Daiki
I built up a small http server and now I want to how I can send data to the browser through the server
jaebie
Can someone help me understan the big three or rule of three in c++ cause its quite hard for me to understand it
jaebie
*understand
Natanim
I'm a beginner c++,
I'm trying to write a program that checks if a record in a file already exists or not through a flag variable. but when i run the program something seems to be off with my code
Natanim
Here is the code:
room.read((char*)&rm, sizeof(rm));
while(!room.eof() || flag==0){
if(rm.roomID==r){
flag=1;
}else{
flag=0;
}
}
if(flag!=1){
rm.roomID=r;
rm.get_record(rm.roomID);
Anonymous
Here is the code:
room.read((char*)&rm, sizeof(rm));
while(!room.eof() || flag==0){
if(rm.roomID==r){
flag=1;
}else{
flag=0;
}
}
if(flag!=1){
rm.roomID=r;
rm.get_record(rm.roomID);
This is not how we do formatted input/output in C++. Read more about formatted IO in C++.
Anyway, in your while loop, you are not reading the file at all. So your while loop may either loop infinitely because you will never reach EOF or because flag == 0.
Anonymous
Can someone help me understan the big three or rule of three in c++ cause its quite hard for me to understand it
There are actually three rules. The Rule of Zero, the Rule of Three and the Rule of 5.
https://en.cppreference.com/w/cpp/language/rule_of_three#:~:text=%5Bedit%5D%20Rule%20of%20three,almost%20certainly%20requires%20all%20three.
Read that. If you still don't understand it, you can ask related questions here rather than asking us to explain a whole big concept.
Anonymous
@Shahar, in the channel link above, you will find a lot of links related to C++ guidelines, clean coding, idioms and patterns.
Anonymous
Is anything between #ifdef X #endif ignored if X is not met?
Yes. #ifdef VAR is equivalent to #if 1 if VAR is defined. It is equivalent to #if 0 otherwise.
Michel
Yes. #ifdef VAR is equivalent to #if 1 if VAR is defined. It is equivalent to #if 0 otherwise.
Yes, thanks, I already tested it and worked ok
Michel
When using CUDA C++, is it necesary/good idea to put all the cudaMalloc inside a class constructor and then all the cudaFree in the destructor?
Anonymous
When using CUDA C++, is it necesary/good idea to put all the cudaMalloc inside a class constructor and then all the cudaFree in the destructor?
Yes it is a good practice. RAII recommends doing so.
But I have not looked at your code. So I assume you are not putting unrelated memory acquisitions in the same class because then it would violate the Separation of Concerns/Single Responsibility Principle. So I am assuming the cudaMalloc and cudaFree calls are related to the actual class you are designing.
Michel
Would appreciate any thoughts on that
Michel
Thanks
'''''''
https://hastebin.com/uqininugec.cpp
this is the code for threesum problem (leetcode#0015)
when I run this code in my vs code with g++(v-12.1.0) I get the desired output but when I run it on online compilers, I only get some part of the output and when I submit on leetcode it throws me this error
'''''''
Line 1034: Char 34: runtime error: addition of unsigned offset to 0x603000000070 overflowed to 0x60300000006c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34
'''''''
Can some one please help?
'''''''
I've checked up the error I get on leetcode and for some it occured when they tried to use variables with garbage values
'''''''
but in my code, I haven't found any such variable
● Igor
Rezoning may, in certain cases, make C# code faster than similarly optimized C++ or C
would that explain why sometimes Java code runs faster than C++?
people say that the JVM is pretty good in that
soheil
Hello to everyone
soheil
I want to start c programming - can someone offer me good book or course? (book is better for me)
soheil
Effective C or A Modern Approach ?
Anonymous
would that explain why sometimes Java code runs faster than C++?
people say that the JVM is pretty good in that
A carefully crafted C/C++ program by a skilled programmer can beat Java's performance any time. But this is not to discount average day to day Java programs running faster. There are many reasons for this. The JIT compiler can optimize and compile bytecodes better than a C/C++ compiler because it has access to information that a C++ compiler doesn't. Also a JIT compiler and a JVM can do a much better job with populating cachelines when running on a target machine with better specs than the host machine on which your code is natively compiled. The folks working on Java's JVM are much better than most of the average day to day C++ programmers which makes it a easy task for Java's speeding up. And the garbage collector can prevent defragmentation of memory which would again help with the data caches. A skilled C++ programmer can do the same with a custom allocator.
But like I said before, if you sit down a skilled C++ programmer with a skilled Java programmer, then you can be sure that her C++ programs will atleast run as fast as the equivalent Java programs if not faster.
Anonymous
Effective C or A Modern Approach ?
If you have never programmed before then C - A modern approach is a better book. If you have programming knowledge then Effective C.
A Modern Approach is a C99 book. It hasn't yet been updated for C11 & C17 standards yet. But if you read that book cover to cover, picking up the changes in C11 or C17 would be pretty easy.
Ludovic 'Archivist'
A carefully crafted C/C++ program by a skilled programmer can beat Java's performance any time. But this is not to discount average day to day Java programs running faster. There are many reasons for this. The JIT compiler can optimize and compile bytecodes better than a C/C++ compiler because it has access to information that a C++ compiler doesn't. Also a JIT compiler and a JVM can do a much better job with populating cachelines when running on a target machine with better specs than the host machine on which your code is natively compiled. The folks working on Java's JVM are much better than most of the average day to day C++ programmers which makes it a easy task for Java's speeding up. And the garbage collector can prevent defragmentation of memory which would again help with the data caches. A skilled C++ programmer can do the same with a custom allocator.
But like I said before, if you sit down a skilled C++ programmer with a skilled Java programmer, then you can be sure that her C++ programs will atleast run as fast as the equivalent Java programs if not faster.
> you can be sure that her C++ programs will atleast run as fast as the equivalent Java programs if not faster
I love how you presuppose the skilled C++ programmer is a she xD
'''''''
https://hastebin.com/uqininugec.cpp
this is the code for threesum problem (leetcode#0015)
when I run this code in my vs code with g++(v-12.1.0) I get the desired output but when I run it on online compilers, I only get some part of the output and when I submit on leetcode it throws me this error
𝕸 could you please have a look at this?
Gani
Can anyone send me Codelite IDE
Gani
Please if u can
Ludovic 'Archivist'
𝕸 could you please have a look at this?
What are you trying to achieve? We can't help you if we do not know that
Ludovic 'Archivist'
Can anyone send me Codelite IDE
are you in a country with internet restrictions?
'''''''
What are you trying to achieve? We can't help you if we do not know that
ohh, I had put the leetcode#0015 for that
anyways, given an array/list of integers, I'm trying to find all the distinct triplets that sum upto 0
Gani
Can u send me ?
Ludovic 'Archivist'
ohh, I had put the leetcode#0015 for that
anyways, given an array/list of integers, I'm trying to find all the distinct triplets that sum upto 0
Then your code is too complicated, you can codegolf that with permutations and accumulate in something like 20 lines of code top
'''''''