4

My C program which uses sorting runs 10x slower the first time than other times. It uses file of integers to sort and even if I change the numbers, program still runs faster. When I restart the PC, the very first time program runs 10x slower. I use time to count the time.

Seth Carnegie
  • 73,875
  • 22
  • 181
  • 249
good_evening
  • 21,085
  • 65
  • 193
  • 298
  • 1
    Is this on linux? If so, it may be storing program information in inactive memory, making the next startup more efficient. That is if the memory is not being allocated dynamically – thatidiotguy Nov 13 '12 at 17:48
  • 1
    To be sure, create 2 files, and run the program with one and then the other. – imreal Nov 13 '12 at 17:51
  • 2
    Any chance of seeing some code? – imreal Nov 20 '12 at 17:39
  • Are you running `time `? If so, what component is taking 10x as long to run? Or, are you using the `time_t time(time_t*);` api? If so, have you tried profiling with gprof or your favorite XCode / Windows profiler to see what functions are taking longer? – rutgersmike Nov 21 '12 at 21:36
  • @RutgersMike I use time – good_evening Nov 21 '12 at 23:12
  • A "hello world" C program runs in 0.123s the first time and 0.008s on each subsequent run on Bash 5.2.2 running on an M1 Macbook Air running macOS 13, compiled with Apple clang 14, as reported by `time`. – Boris Verkhovskiy Oct 29 '22 at 05:38

7 Answers7

17

The operating system holds the data in RAM even if it's not needed anymore (this is called "caching"), so when the program runs again, it gets all data from there and there's no disk I/O. Even when you change the data, that change happens in RAM first, and it stays there even after its written to the file.

It doesn't stay in RAM forever though, mind you. If the memory is needed for something else, the cache is deleted. At that point, a disk access is needed (and it's cached in RAM again at that point.)

This is why first access after a reboot is always slow; the data hasn't been cached yet since it was never read from the file.

Nikos C.
  • 50,738
  • 9
  • 71
  • 96
  • But the input file is randomly generated with same number of data and still the time is similar, why is it like that? Also when I generate with different number of data in file the time when I run it first time is bigger than the others. – good_evening Nov 13 '12 at 17:54
  • @hey When you change the size of the data, the first run on that data does not take 10x longer than subsequent runs, right? – Nikos C. Nov 13 '12 at 18:16
  • Yes, it does take ~10x longer. – good_evening Nov 13 '12 at 18:18
  • I'm guessing the name of the input file is the same? It's faster on subsequent runs because the OS has probably cached the file in memory and you're effectively dealing with a file in RAM. My guess is also that if you wait for some time (browse, play a game, whatever) between subsequent runs, the run time is approximately the same and not 10x less. – Carl Nov 22 '12 at 02:02
  • @bye Is the input file generated each time before you run your program? Also before the first time after computer booted? Or are you booting the computer and reading the file that was already present when the computer was booted? – Werner Henze Nov 22 '12 at 16:43
  • My "hello world" program is compiled to 16887 bytes and runs in 51ms the first time vs 8ms subsequent times. Even if my SSD reads 500MB/s, it [would take](https://www.wolframalpha.com/input?i=17KB+at+500+MB%2Fs) like 40-80 microseconds to load 17KB, so that can't account for the 40 millisecond difference. – Boris Verkhovskiy Mar 16 '23 at 08:19
3

You have to make hypothesis and confront them to reality. The first you can reasonably make is that it does smell a lot like a caching issue !

Ask yourself those questions :

  • Does my data fits in free RAM (= is my file cached by the OS FS cache ?)
  • Does my data fits in CPU data cache ?

  • Does my data fits in HDD internal cache ?

    1. The most easy hypothesis to discard is the FS cache. Under linux, just issue sync; echo 3 > /proc/sys/vm/drop_caches between each call to your program. The first will make sure the cached data will make it to the physical medium (hard drive), the second will drop the content of the filesystem cache from memory.

    2. The 'physical medium' might be the HDD cache itself, so beware... Under linux you can disable this "write-back" cache with the command hdparm -W 0 <device>, for instance if you are working with drive sda, hdparm -W 0 /dev/sda will do the job. You might want to re-enable it after you are finished with your tests :)

    3. Another hypothesis is the CPU cache, have a look at How can I do a CPU cache flush in x86 Windows? and How to clear CPU L1 and L2 cache

Well, it may or may not be one of those, but it doesn't hurt trying :)

Community
  • 1
  • 1
Erwan Queffélec
  • 716
  • 1
  • 6
  • 20
1

If your program does network access then that could be the reason for the initial delay. Many network protocols need time to setup things. Some examples:

  • DNS: if your program does any network access, chances are it needs to resolve a hostname to an IP address. The first time it would need at least a network round trip to populate a local cache. Following requests would be shorter.
  • Networked filesystems (NFS, CIFS and others): opening files can happen through the network.
  • Even some seemingly innocuous library functions can require network access: the users list for the host can be on a remote directory server.

Appart from this you could use some low level tracing tool to see where the time is spent. On linux a basic tool is strace -r. There is probably some similar tool for other systems. Your compiler must also come with a profiler (i.e. gprof for GCC or maybe Valgrind).

kmkaplan
  • 18,655
  • 4
  • 51
  • 65
1

I had a very similar issue but I wasn't loading in a large file - so I was baffled at the long first execution time (caching couldn't have been the issue).

This answer pointed me in the right direction - it was my real-time anti-virus protection. Every time I recompiled the program it would re-scan it as being potentially malicious. I added my project path as an "Exception" to Avira's (in my case) real-time virus protection.

Program execution on the first execution is now lightening quick!

Rohan
  • 507
  • 1
  • 4
  • 15
0

This is nothing new, not just your program many popular commercial softwares face this problem.

To start with check this MATLAB Article about slow fist time execution

In case of other programming language which runs on a Virtual Machine like C# or Java this is quite common. http://en.wikipedia.org/wiki/Just-in-time_compilation#Startup_delay_and_optimizations

Caching is a good reason for that to happen in C but still 10x is quite a long duration..It might be also possible that you system was loading other resources after you restart.

You should run the program after say 10 minutes after restart for better results. All the startup application would be loaded by that time. (10 minutes ---- depends on the number of startup applications and the time it takes to start each of them)

AurA
  • 12,135
  • 7
  • 46
  • 63
0

This is because of compiler optimatization ,what it does is it caches the result for Temoparal Locality and the activation record is saved,time is also saved because the binding object donot have to be reloaded again during Linking Stage

nightrider
  • 95
  • 8
0

There are two components to the time measured

If you are reading a file from disk,and loading it in memory - and sorting :

1)Time to read the file & store it in an array 2)Time of sorting

Were these measured separately?

Can you check this out? Invalidating Linux Buffer Cache

Instead of doing a restart, if repeating the experiment with clearing the cache gives the same result, then you can infer that File buffer caching effects were not factored into.

Arvind
  • 466
  • 3
  • 9