Manju
Hey pls allow me to write
Manju
Bot
Manju
i mean for learning low level or even working with low level devices, C is quite helpful
Will u pls allow me to to write without restriction?
Manju
I hate this bot
Never Spam Bot
Spookistud is now approved by the group admin and can send messages without any restrictions
Wanna learn debugging
See spam? Quote the spam message in the group and reply with /spam
klimi
there you go
Manju
Well my senior dev said me :-
Create a prototype small app that reproduce same bug as ours .. well we can't show our source code as it's private and for security reasons and moreover they said to post it in stack overflow or reddit or twitter so that someone who knows how to solve that bug will easily solve it via seeing our dummy app ....
Well after that he gave me some tips like always document it what and how u find the solution to debug ur code
Use git lens to see and understand the code and then give pr number of that
Well I am beginner never been in corporate before .. tbh all in my mind was going what the hell is saying because I never used debugging .. kind of u can say I am just intern 👍 hoping to get some answers
Lot of questions arise in my mind 🤯
Pavel
Well my senior dev said me :-
Create a prototype small app that reproduce same bug as ours .. well we can't show our source code as it's private and for security reasons and moreover they said to post it in stack overflow or reddit or twitter so that someone who knows how to solve that bug will easily solve it via seeing our dummy app ....
Well after that he gave me some tips like always document it what and how u find the solution to debug ur code
Use git lens to see and understand the code and then give pr number of that
Well I am beginner never been in corporate before .. tbh all in my mind was going what the hell is saying because I never used debugging .. kind of u can say I am just intern 👍 hoping to get some answers
Lot of questions arise in my mind 🤯
Sounds tough, but I'm sure you can learn a lot from it.
If you have C/C++ related questions, then ask them (just be sure to google first, google is your friend)
0100110010100010
Hi guys how easy solve of algorithms on c?
~
Does anyone know how to use dynamic arrays in C, or library for that? I have searched on Google and found out that C does not have dynamic arrays. It says I have to implement runtime dynamic resizing myself, but I am still a newbie. I tried it, but I got confused >< I want something that equal to vector
Vlad
Vlad
It might be good enough for your case
~
You can use realloc as a start
Can you give strategy how is the implementation? because I am afraid it will not become optimized or correct implementation if I do it without some info, and I will not notice the mistake. I search in google, it tells me to double the alloc with realloc if capacity is full, how about your method?
Vlad
Can you give strategy how is the implementation? because I am afraid it will not become optimized or correct implementation if I do it without some info, and I will not notice the mistake. I search in google, it tells me to double the alloc with realloc if capacity is full, how about your method?
I have no idea what your task is
Vlad
But realloc is already implemented to be used as a vector
Vlad
In any modern c standard lib implementation
Vlad
More over it's written in highly optimized assembly
Vlad
Unless you really need custom implementation you should leave it as is
Vlad
For that you need profiling and benchmarking to know that it's the culprit
Vlad
Or realloc does not suite your allocation strategy for whatever system you are making then you would know
Vlad
Or realloc does not suite your allocation strategy for whatever system you are making then you would know
Then it's more of a 'custom allocator' territory upon which you write your own realloc
Chat Boss
Then it's more of a 'custom allocator' territory upon which you write your own realloc
~ sent a code, it has been re-uploaded as a quote
Can you verify my code sir because my vector push speed onpar and beat C++ vector a little bit, so I think it has incorrect implementation 😅 here is my code
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <string.h>
typedef struct {
int* val;
size_t size;
size_t capacity;
} Vec;
void vec_init(Vec* v){
v->val = NULL;
v->size = 0;
v->capacity = 0;
}
int vec_push(Vec* v, int input){
if (v->size == v->capacity){
size_t new_capacity = (v->capacity == 0) ? 4 : v->capacity * 2;
int* new_val = (int*)realloc(v->val, new_capacity * sizeof(int));
if (!new_val) return -1;
v->val = new_val;
v->capacity = new_capacity;
}
v->val[v->size++] = input;
return 0;
}
void vec_clear(Vec* v){
v->size = 0;
}
void vec_free(Vec* v){
free(v->val);
v->val = NULL;
v->size = 0;
v->capacity = 0;
}
int program(){
Vec data;
vec_init(&data);
struct timeval start, end;
gettimeofday(&start, NULL);
for (int i=0; i<10000; i++){
vec_push(&data, i);
}
gettimeofday(&end, NULL);
long elapsed_us = (end.tv_sec - start.tv_sec) * 1000000L + (end.tv_usec - start.tv_usec);
printf("time needed: %d us\n> ", elapsed_us);
vec_free(&data);
}
int main(){
int running = 1;
char input[100];
printf("type run to run and rerun\n> ");
while (running){
scanf("%s", input);
if (strcmp(input, "run") == 0){
program();
} else {
printf("failed to run program\n");
break;
}
}
return 0;
}
Chat Boss
~ sent a code, it has been re-uploaded as a quote
Here is my C++ version
#include <iostream>
#include <string>
#include <vector>
#include <bit>
#include <chrono>
void program(){
std::vector<int> data;
auto start = std::chrono::high_resolution_clock::now();
for (int i=0; i<10000; i++){
data.push_back(i);
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << duration.count() << " us\n> ";
}
int main(int argc, char* argv[]) {
bool running = true;
std::string input;
std::cout << "Usage: type run to run and rerun\n> ";
std::cout.flush();
while (running) {
if (!std::getline(std::cin, input)) {
return 0;
}
if (input == "run") {
program();
} else {
return 0;
}
}
}
~
The result is like this
My C :
type run to run and rerun
> run
time needed: 67 us
> run
time needed: 30 us
> run
time needed: 57 us
> run
time needed: 57 us
> run
time needed: 57 us
> run
time needed: 58 us
> run
time needed: 58 us
> run
time needed: 58 us
> run
time needed: 57 us
> run
time needed: 57 us
> run
time needed: 56 us
> ^C[uwu@localhost c]#
My C++ :
Usage: type run to run and rerun
> run
577 us
> run
63 us
> run
43 us
> run
69 us
> run
61 us
> run
62 us
> run
48 us
> run
62 us
> run
61 us
>
~
After doing some random edits :v I realized that the “size * 2” trick is what makes it fast, because it preallocates double the current size and avoids frequent realloc calls. But then I just realized that doubling the current size can waste a lot of memory. For example, if the current vector size is 100 and the total memory consumed by the vec is 1 GB, and I just need space for 1 more value, so the new size would be 101, doubling would allocate 2 GB instead of just enough for that 1 value. That is a whole 1 extra GB RAM wasted :(
So I changed it to just current size + 4. The result is the performance dropped drastically, about 3 - 6 times slower than C++ vector 🤣
type run to run and rerun
> run
time needed: 403 us
> run
time needed: 352 us
> run
time needed: 351 us
> run
time needed: 351 us
> run
time needed: 351 us
> run
time needed: 350 us
> run
time needed: 350 us
> run
time needed: 349 us
> run
time needed: 351 us
> run
time needed: 281 us
> run
time needed: 351 us
> run
time needed: 412 us
> run
time needed: 349 us
> run
time needed: 134 us
>
Pavel
After doing some random edits :v I realized that the “size * 2” trick is what makes it fast, because it preallocates double the current size and avoids frequent realloc calls. But then I just realized that doubling the current size can waste a lot of memory. For example, if the current vector size is 100 and the total memory consumed by the vec is 1 GB, and I just need space for 1 more value, so the new size would be 101, doubling would allocate 2 GB instead of just enough for that 1 value. That is a whole 1 extra GB RAM wasted :(
So I changed it to just current size + 4. The result is the performance dropped drastically, about 3 - 6 times slower than C++ vector 🤣
type run to run and rerun
> run
time needed: 403 us
> run
time needed: 352 us
> run
time needed: 351 us
> run
time needed: 351 us
> run
time needed: 351 us
> run
time needed: 350 us
> run
time needed: 350 us
> run
time needed: 349 us
> run
time needed: 351 us
> run
time needed: 281 us
> run
time needed: 351 us
> run
time needed: 412 us
> run
time needed: 349 us
> run
time needed: 134 us
>
Allocations are very expensive, if you know the amount of elements you're going to get, you should allocate for this amount of elements.
std::vector has a reserve method for that. You should call it before doing your for loop of push_backs.
~
Allocations are very expensive, if you know the amount of elements you're going to get, you should allocate for this amount of elements.
std::vector has a reserve method for that. You should call it before doing your for loop of push_backs.
Yeah, but in the real world, the amount of data is usually not fixed. For example, when fetching from a database, it could return 1000 rows, 5000 rows, or 2500 rows. I just want a dynamic contigous container like vector in C that is on par with C++’s std vector, that can still perform on par even without preallocation
~
I think I got your point. I can pass the total number of affected rows returned by the database query and use that for preallocation. But when my vector faces a case where I can not preallocate exactly because the number of items is not known, the performance will still drop, do you have any tips for that?
Pavel
I think I got your point. I can pass the total number of affected rows returned by the database query and use that for preallocation. But when my vector faces a case where I can not preallocate exactly because the number of items is not known, the performance will still drop, do you have any tips for that?
Usually you decide based on the specific requirements, limitations and common patterns; and if you don't know the requirements, you give some levers of control to the user of your class/library.
As an example of requirements, it may be that you must have an average insertion time below some time, or your requirement may be that you can't spend more than some time on the insertion (maximum instead of average). Or maybe the time is not as important but you shouldn't waste extra memory. There may be other requirements that could affect the design decisions, like whether other operations on the container should be optimized for, whether objects should never be moved, etc.
A limitation may be that you know how many elements there could be at max (e.g. having more would be a logical error, e.g. more than 6 sides of a cube, more than 7 days in a week). This one sometimes is difficult to balance not to explode your next rocket https://en.m.wikipedia.org/wiki/Ariane_flight_V88
A pattern could be for example, that the elements are often inserted in batches of specific size, or the size of the container usually caps at some size and then the elements are reused. Or there is known the most common amount of elements or their size.
For the exposed levers, std::vector exposes functions like resize, reserve, size, and capacity that allow to move all the decisions about memory allocation to the user side, so if the user of std::vector needs to and knows how to better optimize the allocation strategy, they can do that.
Pavel
Usually you decide based on the specific requirements, limitations and common patterns; and if you don't know the requirements, you give some levers of control to the user of your class/library.
As an example of requirements, it may be that you must have an average insertion time below some time, or your requirement may be that you can't spend more than some time on the insertion (maximum instead of average). Or maybe the time is not as important but you shouldn't waste extra memory. There may be other requirements that could affect the design decisions, like whether other operations on the container should be optimized for, whether objects should never be moved, etc.
A limitation may be that you know how many elements there could be at max (e.g. having more would be a logical error, e.g. more than 6 sides of a cube, more than 7 days in a week). This one sometimes is difficult to balance not to explode your next rocket https://en.m.wikipedia.org/wiki/Ariane_flight_V88
A pattern could be for example, that the elements are often inserted in batches of specific size, or the size of the container usually caps at some size and then the elements are reused. Or there is known the most common amount of elements or their size.
For the exposed levers, std::vector exposes functions like resize, reserve, size, and capacity that allow to move all the decisions about memory allocation to the user side, so if the user of std::vector needs to and knows how to better optimize the allocation strategy, they can do that.
That said, it is also important to distinguish actual requirements from imaginary ones. If you don't have to optimize for some specific requirement, it is often a good idea to have a good average case and keep the code simple, so the developer who comes to this code after, having actual requirements at hand (e.g. you in the future) has an easier time changing this code for their case.
In this case multiplying by 2 may be a good thing for a generic average case, and simple enough to change later. Most times keeping algorithmic complexity reasonably low could be a good choice. Though it is also difficult to balance sometimes (but that's why we (software engineers) are here).
mito
~
Usually you decide based on the specific requirements, limitations and common patterns; and if you don't know the requirements, you give some levers of control to the user of your class/library.
As an example of requirements, it may be that you must have an average insertion time below some time, or your requirement may be that you can't spend more than some time on the insertion (maximum instead of average). Or maybe the time is not as important but you shouldn't waste extra memory. There may be other requirements that could affect the design decisions, like whether other operations on the container should be optimized for, whether objects should never be moved, etc.
A limitation may be that you know how many elements there could be at max (e.g. having more would be a logical error, e.g. more than 6 sides of a cube, more than 7 days in a week). This one sometimes is difficult to balance not to explode your next rocket https://en.m.wikipedia.org/wiki/Ariane_flight_V88
A pattern could be for example, that the elements are often inserted in batches of specific size, or the size of the container usually caps at some size and then the elements are reused. Or there is known the most common amount of elements or their size.
For the exposed levers, std::vector exposes functions like resize, reserve, size, and capacity that allow to move all the decisions about memory allocation to the user side, so if the user of std::vector needs to and knows how to better optimize the allocation strategy, they can do that.
I changed it with this strategy :) when total allocated is below 50 mb, it uses current size * 2, but when it is above 50 mb it will automatically uses current size + 8 (increment the size 8 by 8) I am not sure if it good too 😅
~
I mean isn't that how it should be done?
You can probably check this.
https://github.com/eteran/c-vector
Yeah but it has a cons (potentially wasted memory) for example, if current size is 1000, then just needing to push 1 more time, the size if full so it will double 1000 * 2 = 2000, but only 1001 is used, the rest 999 is wasted
~
But I am not sure about benchmarking with time now - time before. Is it accurate? is there more accurate method?
Chat Boss
~ sent a code, it has been re-uploaded as a quote
Because I just recreated the same code in javascript, take a look if this is coorect or not
const readline = require("readline")
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
function program(){
let data = []
const start = performance.now()
for (let i=0; i<10000; i++){
data.push(i)
}
let end = performance.now()
end = end - start
console.log(Elapsed time: ${(end * 1000).toFixed(0)} us\n);
}
async function main(){
while (true){
const input = await new Promise((resolve) => {
rl.question("> ", (input) => {
resolve(input.trim())
})
})
switch (input){
case "run":
program()
break
default:
break
}
}
}
main()
Somehow javascript JIT is very fast doing push to dynamic array (notice the duration gets very fast after iterations, is it hint the JIT has done its job?)
[root@localhost js]# node main.js
> run
Elapsed time: 2514 us
> run
Elapsed time: 15026 us
> run
Elapsed time: 608 us
> run
Elapsed time: 673 us
> run
Elapsed time: 260 us
> run
Elapsed time: 258 us
> run
Elapsed time: 308 us
> run
Elapsed time: 355 us
> run
Elapsed time: 148 us
~
It is just 3 times slower than C++ std vector, and faster than my previous C with 4 increment resizing ><
Orange Juice
DSA in C++ or java?
Ujjawal
Is C not a good choice for DSA?
klimi
After doing some random edits :v I realized that the “size * 2” trick is what makes it fast, because it preallocates double the current size and avoids frequent realloc calls. But then I just realized that doubling the current size can waste a lot of memory. For example, if the current vector size is 100 and the total memory consumed by the vec is 1 GB, and I just need space for 1 more value, so the new size would be 101, doubling would allocate 2 GB instead of just enough for that 1 value. That is a whole 1 extra GB RAM wasted :(
So I changed it to just current size + 4. The result is the performance dropped drastically, about 3 - 6 times slower than C++ vector 🤣
type run to run and rerun
> run
time needed: 403 us
> run
time needed: 352 us
> run
time needed: 351 us
> run
time needed: 351 us
> run
time needed: 351 us
> run
time needed: 350 us
> run
time needed: 350 us
> run
time needed: 349 us
> run
time needed: 351 us
> run
time needed: 281 us
> run
time needed: 351 us
> run
time needed: 412 us
> run
time needed: 349 us
> run
time needed: 134 us
>
i don't think that this allocated memory is necessary wasted, if it is not used it probably doesn't have physical pages
0100110010100010
Guy and take algorithms in development?
Vlad
Vlad
With plenty of address space
Vlad
You get continuous block of virtual address space that OS yanks in memory for you on pagefaults
aryoassamirg
hey guyzz
hey guyzz
Don't ask meta questions. In other words, don't ask to ask. Questions like "Does anyone know XYZ?", "Has anyone used XYZ?" or "Can someone help me?" are all considered meta questions because they don't specify what your actual problem is.
These questions give the impression that you want people to approach you and offer their help as if they don't have any other work to do. Now doesn't that expectation make you look like an idiot?
If you have a question ask it directly. You are more likely to get a response that way.
User 来财@阿里云充值就送 has 1/2 warnings; be careful!
Reason:
offtopic ad
Jojo
I have just sought out the first edition of"The C programming language" and as I was reading the preface there is a paragraph noting that the book is not an introductory programming manual, this being said am wondering which is a good reference to introductory programming manual in line with the 1978 edition
Jojo
I have just sought out the first edition of"The C programming language" and as I was reading the preface there is a paragraph noting that the book is not an introductory programming manual, this being said am wondering which is a good reference to introductory programming manual in line with the 1978 edition
I found the 1st ed is easier for me to understand than the ansi c