Yes, you can consider the algorithmic complexity of your code, which is independent of any hardware.
this post was submitted on 02 Dec 2023
5 points (100.0% liked)
Advent Of Code
763 readers
1 users here now
An unofficial home for the advent of code community on programming.dev!
Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.
AoC 2023
Solution Threads
| M | T | W | T | F | S | S |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | ||||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 |
Rules/Guidelines
- Follow the programming.dev instance rules
- Keep all content related to advent of code in some way
- If what youre posting relates to a day, put in brackets the year and then day number in front of the post title (e.g. [2023 Day 10])
- When an event is running, keep solutions in the solution megathread to avoid the community getting spammed with posts
Relevant Communities
Relevant Links
Credits
Icon base by Lorc under CC BY 3.0 with modifications to add a gradient
console.log('Hello World')
founded 1 year ago
MODERATORS
Sure, but that makes a lot of optimizations nonexistent (e.g. cloning the input on an O(n) algorithm is "free")
You don't need to use big-O. You can calculate the full complexity in algebraic notation. It's just a lot more work as you don't get to discard terms.
Im theory you could try counting CPU cycles or something analogous, or algorithmic complexity as the other commenter mentioned. You could also try to measure it in comparison to different code.
Outside of that, and in any practical sense, no you can't. Performance measurements are dependent on the machine as much as the software.
If a car is hardware, and the driver is software, how would you measure the performance of the driver in the different cars? The only way I can think of is if you had 2 different drivers and could compare their times in both cars. If driver 1 is 2x as fast in car 1, and 2x as fast in car 2, you could say driver 1 has a score 2x higher than driver 2.
CPU cycles depend on the instruction set of the hardware. This would also require compilation without any optimization to avoid even software dependency.
One option could be to emulate a full CPU and run it on that, and count the cycles on that. One issue is linking/syscalls. Maybe compiling to smth like WASM could work?
I would be interested to hear if you get far down that road. It sounds infinitely more difficult than running code and timing it.
Are you able to expand what problem lead you to this question (out of curiosity)?
Friend and I are comparing times, but since he uses Jai, I can't compile his.
As an alternative could he compile your program?
perf and valgrind might be good places to start. Although, some programs aren't going to have the exact same executed instruction count between runs, and it's possible that executed instruction count can depend on the exact CPU that's running. You can probably mitigate the latter by running valgrind and the program inside of QEMU.
Thank you! That's exactly the kinda thing I was looking for!
I believe everyone gets different input and needs to produce a different result. There can be multiple solutions. Do you process as you are going, or do you parse and build a data structure to process later so you loop through the results multiple times.