While competing on a competitive coding websites, I formulated a solution which implemented Tries. For which I had to dynamically allocate heap memory during run-time. The solution couldn't get accepted as it crossed the time limit of 1 sec by 0.12 seconds. In the solution code, they did not allocate any heap memory and used arrays instead to build Tries. The run-time of this code was ~0.79 seconds. What can be the reason ?
Asked
Active
Viewed 1,649 times
1
-
Yes. It increases runtime, as it is a system call. – Nawaz Sep 22 '15 at 05:58
-
3Like hundred million thing, can you show us some equivalent code? – Melkon Sep 22 '15 at 05:58
-
1A general suggestion: when it's about performance there are tools called profilers which will tell you quite precisely where the problem could be and sometimes the results are a lot different from what you expect and another even more general suggestion: do not guess when you can have solid empirical answers quite easily. – Marco Sep 22 '15 at 08:22
-
You're not really understanding C++ if you think "allocate heap memory" and "use arrays" are mutually exclusive. `new int[5]` allocates an array on the heap. – MSalters Sep 22 '15 at 08:26
-
@MSalters please take a look at [link](http://stackoverflow.com/questions/161053/which-is-faster-stack-allocation-or-heap-allocation) .It states that stack allocation is much faster. – markroxor Sep 22 '15 at 11:15
-
@markroxor: I posted an answer there, I know the question. it's irrelevant. "heap" and "stack" are generally considered mutually exclusive, but "use arrays" is entire unrelated to the "heap vs stack" discussion. – MSalters Sep 22 '15 at 11:28
1 Answers
3
Yes it is likely the heap allocation added overhead - it could also be your algorithm.
See eg. Which is faster: Stack allocation or Heap allocation, for some hints of the costs of heap allocation.
You could typically reduce the overheads by allocating a pool of objects at once (and releasing to the pool instead of delete) instead of frequent malloc/new. This is one technique among many. See eg. https://msdn.microsoft.com/en-us/library/ms810466.aspx for some others.
