Hacker Read

yxhuvud · 2016-10-29 07:31:31+00:00

Malloc is O(n²) so it totally depend on how able you are to not do gradual allocation.

remexre | karma 1273 | avg karma 2.23 · | 2021-12-22 20:35:48

malloc isn't typically O(n) though, so I don't think that's reasonable math?

chopin | karma 3564 | avg karma 2.52 · | 2022-08-09 17:13:40

Afaik, a malloc is not guaranteed to return fast. With those requirements it's hard even in C.

coliveira | karma 8490 | avg karma 2.38 · | 2015-01-30 22:24:00+00:00

malloc is a generic allocator, it needs to worry about a lot of things that are not common. A simple allocator will work most of the time, but the devil is in the details.

LessDmesg | karma 45 | avg karma 0.19 · | 2019-12-10 06:40:42+00:00

malloc() isn't O(1), but allocations in a normal GC are O(1).

joosters | karma 15062 | avg karma 4.78 · | 2013-12-04 20:14:10+00:00

There's a huge depth to a good malloc() implementation. While you're wise to avoid it when your interests are focused on kernel development, I'd recommend every programmer to have a go at writing malloc/free one day. Avoiding terrible performance problems is pretty tricky. At the very least, you'll gain a lot of respect for memory allocation and will discover that there's a lot of work going on behind the scenes when your code tries to allocate only a few bytes of memory.

lisper | karma 54803 | avg karma 4.63 · | 2022-08-25 19:03:35

Sure. But in general both malloc and cons are pretty zippy most of the time.

faragon | karma 1122 | avg karma 1.25 · | 2016-10-29 08:08:06+00:00

In most C libraries malloc() is O(log n), e.g. when implemented as balanced trees.

yencabulator | karma 2815 | avg karma 0.85 · | 2020-11-23 03:19:26+00:00

malloc isn't magic, just mmap some memory to dole out.

Asooka | karma 1643 | avg karma 0.98 · | 2017-05-18 07:24:18

malloc already hands you more than you ask for in a lot of cases, check out malloc_usable_size.

CyberDildonics | karma 3006 | avg karma 0.57 · | 2017-08-19 00:52:29+00:00

Are you aware that malloc() is slow and doing all these tiny allocations is probably the biggest bottleneck in your program?

gdwatson | karma 437 | avg karma 2.71 · | 2016-04-12 21:12:21+00:00

That would require implicit heap allocation, which is a lot to ask for in a language where malloc is a library function.

mhh__ | karma 13345 | avg karma 1.95 · | 2021-06-15 07:26:32+00:00

Malloc is at best a few hundred cycles, that's quite a lot of work if you can keep your data in L1. If you do a bit of work now you can save reallocs later.

Think bigger than changing the coefficient, there probably is no optimal factor.

reply

rumcajz | karma 4600 | avg karma 5.5 · | 2017-04-23 09:20:22

My rule of thumb is to look at application's design and only ever use malloc where there is 1:N (or N:M) relationship between entities. Everything that's 1:1 should be allocated in a single step.

jcranmer | karma 30697 | avg karma 4.25 · | 2018-08-10 10:24:28

Malloc will still fail for overly large allocation sizes. If you try to malloc(-1), for example.

david-given | karma 7108 | avg karma 4.5 · | 2016-03-13 13:13:47

In such an environment, malloc() will do that.

dllthomas | karma 14749 | avg karma 1.38 · | 2014-01-31 18:08:37

The same thing can be said about malloc. It's a matter of degree, and different projects have (sometimes subtly) different requirements.

TheLoneWolfling | karma 1750 | avg karma 1.05 · | 2015-07-13 12:37:37

Any idea how much space overhead malloc has with entries as small as this? (<1 to 4> * 8 bytes)

Seems to me it could easily be a significant amount of overhead.

reply

fermentation | karma 595 | avg karma 3.52 · | 2020-12-13 03:46:56+00:00

Yes as it turns out malloc is much faster if free doesn’t exist.

ekidd | karma 9965 | avg karma 10.34 · | 2011-02-16 09:25:18

Really? One allocation every 50 to 100ms? That would mean you could only do 10 to 20 memory allocations per second. Now, I know that malloc is often very slow, but that seems unlikely.

Or do you mean 50 to 100 microseconds? That's still horrible, but I could believe it.

reply