Suggestions for my mallocator

[CBFalconer]

Well more importantly, you can choose the ordering in which a sequence
of allocations is freed, and therefore can always create whatever kind
of fragmentation you like. So this clearly is not one of the criteria
a C-style allocator can have.

If we could move the storage (see next para) this can be handled.
In ISO Pascal we know there are no extant pointers other that those
assigned by new, so indirection and repacking is possible.

[...] Any such
would require indirect memory access for everything, which would be
a monstrous performance hit when enforced, together with
specialized compilers (or interpreters). However it is definitely
possible to have O(1) performance for all operations and to always
recover memory.

Ok, but what about also always being able to successfully allocate?

[...] It doesn't even require buddy systems (which have
their own penalties). I have published such a system, which only
requires care in writing.

See <http://cbfalconer.home.att.net/download/nmalloc.zip>

I noticed you don't supply any seperate documentation for it. Can I
assume the comments in the code are accurate? From what I can peruse:

As far as I know they are accurate. Not the memalign portion,
which is nonsense as published (and so labelled).

1) You seem to be neglecting at least one merge scenario. When you
split off the excess from an allocation, you are not merging it with
any possible adjacent free entries. In a sense this causes unnecessary
fragmentation of the remaining free entries. Remember with your
strategy, you want your free entries to be as large as possible. Try
writing a benchmark with a lot of reallocs in it, and you will see the
difference this makes.

Not so. The split off portion is always merged if possible. If
too small to be of use it is included in the assigned memory. One
of us is wrong Just such a test exists in the testing code.

2) Your function size2bucket() is a linear search (though, of course,
its count is bounded above by sizeof(ulong)*CHAR_BITS). Think about it
as bits but seperated from the mathematical properties for a second.
You can re-implement it using a binary search, which means on real
system you would have an effective loop count of 5 or 6.

For a search of roughly 16 or 20 items (at most), this is not
useful. Notice that the search begins at the first guaranteed
suitable bucket, and there is no need to search the list of bucket
items. This makes it approximately a first fit algorithm.

3) You are also giving up as soon as your algorithm is unable to find
memory using its "fast method". If you run out of memory, you are in
typically in "screwedzville" anyways. You can simply go back to your
free list and check the bucket one lower, and start scanning linearly
for some fixed amount before truly bailing. This is important for
certain scenarios where you are allocating near the system limit in
terms of amount of memory, but nearly all your allocations are the
exact same size (this scenario is very typical). With your strategy as
coded, you can "run out of memory" even though you actually have plenty
of memory available -- you just aren't willing to scan for it. Its
very difficult to implement something which works robustly and all the
time here, but you can capture typical cases without too much effort.

It won't be 'plenty'. It may exist in the lower bucket, but that
would involve searching a list of unknown length, requiring unknown
time. The system hasn't aborted, it just returns NULL, so the user
has an opportunity to take corrective action. If the system has
reached that point total inability is near anyhow, but the
capability of making smaller assignments MAY still be present, to
assist in recovery.

Notice that when that mechanism fails the opportunity to grab more
memory from the OS still exists, via sbrk.

In any event, it is as I said. You can implement something with O(1),
but it ends up not always being able to allocate all available memory
successfully.

And, as I said, doing such requires moving previously assigned
memory and repacking. The fundamentals of C make this
impracticable.

The whole thing should port easily to any system where alignment
depends on the low order bits of the addresses and arithmetic on
such addresses is valid. The other dependency is on the sbrk
routine. Thus it should work for most *IX systems. The variadic
development debuggery macros require gcc to avoid bombing even when
they are switched off.

 

[websnarf]

Well more importantly, you can choose the ordering in which a sequence
of allocations is freed, and therefore can always create whatever kind
of fragmentation you like. So this clearly is not one of the criteria
a C-style allocator can have.

If we could move the storage (see next para) this can be handled.
In ISO Pascal we know there are no extant pointers other that those
assigned by new, so indirection and repacking is possible.

[...] Any such
would require indirect memory access for everything, which would be
a monstrous performance hit when enforced, together with
specialized compilers (or interpreters). However it is definitely
possible to have O(1) performance for all operations and to always
recover memory.

Ok, but what about also always being able to successfully allocate?

[...] It doesn't even require buddy systems (which have
their own penalties). I have published such a system, which only
requires care in writing.

See <http://cbfalconer.home.att.net/download/nmalloc.zip>

I noticed you don't supply any seperate documentation for it. Can I
assume the comments in the code are accurate? From what I can peruse:

As far as I know they are accurate. Not the memalign portion,
which is nonsense as published (and so labelled).

1) You seem to be neglecting at least one merge scenario. When you
split off the excess from an allocation, you are not merging it with
any possible adjacent free entries. In a sense this causes unnecessary
fragmentation of the remaining free entries. Remember with your
strategy, you want your free entries to be as large as possible. Try
writing a benchmark with a lot of reallocs in it, and you will see the
difference this makes.

Not so. The split off portion is always merged if possible. If
too small to be of use it is included in the assigned memory. One
of us is wrong Just such a test exists in the testing code.

Hmm ... you threw the combine call in the mv2freelist() but didn't
document the fact that a merge was taking place. You need better
comments -- including one that explains where mv2freelist() is called
from and why it only needs to perform one direction of combine instead
of testing for both.

For a search of roughly 16 or 20 items (at most), this is not
useful.

You don't notice that 16/6 = 2.666 < c < 20/5 = 4 which is a lot larger
than 1? Look, I've written my own very similar allocation scheme, I
threw a profiler on it, and this calculation always turns out to be a
white-hot hot spot.

[...] Notice that the search begins at the first guaranteed
suitable bucket, and there is no need to search the list of bucket
items.

Huh? It starts at sz and shifts off bits one at a time. I don't know
what you are talking about here.

[...] This makes it approximately a first fit algorithm.

Whatever, you are trying to perform a ceil(lg2()), and you aren't doing
it very well.

It won't be 'plenty'.

It can be arbitrarily plenty. Look, simply allocate a fixed sized
element over and over until you run out of memory. Then just free
every other allocation (so no merging takes place, but basically half
your memory is reclaimed.) Then simply try to allocate 1 entry again
with that fixed size. You will fail because the free list only
contains elements from the tightly fitting bucket rather than the one
one greater.

[...] It may exist in the lower bucket, but that
would involve searching a list of unknown length, requiring unknown
time.

To guarantee it, yes -- so don't provide a guarantee. Just search a
small finite number of elements before giving up. The point is that
the vast majority of scenarios where the memory is being pushed this
far, the size of the memory dominating data structures are still likely
to be uniform.

[...] The system hasn't aborted, it just returns NULL, so the user
has an opportunity to take corrective action.

My point is that its returning NULL too soon. And as you well know,
corrective action is typically "exit(EXIT_FAILURE ...)". Staving off
the need should be a priority.

[...] If the system has
reached that point total inability is near anyhow, but the
capability of making smaller assignments MAY still be present, to
assist in recovery.

Notice that when that mechanism fails the opportunity to grab more
memory from the OS still exists, via sbrk.

I am talking about the scenario after sbrk() runs out of more system
memory as well.

 

[CBFalconer]

.... snip critique of

It won't be 'plenty'.

It can be arbitrarily plenty. Look, simply allocate a fixed sized
element over and over until you run out of memory. Then just free
every other allocation (so no merging takes place, but basically half
your memory is reclaimed.) Then simply try to allocate 1 entry again
with that fixed size. You will fail because the free list only
contains elements from the tightly fitting bucket rather than the one
one greater.

[...] It may exist in the lower bucket, but that would involve
searching a list of unknown length, requiring unknown time.

To guarantee it, yes -- so don't provide a guarantee. Just search a
small finite number of elements before giving up. The point is that
the vast majority of scenarios where the memory is being pushed this
far, the size of the memory dominating data structures are still
likely to be uniform.

[...] The system hasn't aborted, it just returns NULL, so the user
has an opportunity to take corrective action.

My point is that its returning NULL too soon. And as you well know,
corrective action is typically "exit(EXIT_FAILURE ...)". Staving off
the need should be a priority.

Yes, that is a reasonable possibility (the finite search). I guess
the case could arise from implementing a list with header nodes,
and destroying alternate entries. I think it is well enough
structured that the place to inject such code is obvious.

Another eventual improvement might be to separate out entirely all
allocations under, say, 16 or so bytes, and perform them from a
separate chunk. The purpose being to avoid the overhead of the
control field for small allocations. This is more complicated.

 

[nfwavzrdvwl]

You seem to be under a misapprehension. Nothing is being stolen.

 

[nfwavzrdvwl]

Or you can buy the whole book and reward the authors' effort.

I think that's an excellent thing to do, and I happily buy books...
however, I don't have unlimited funds to buy books. When I need the
information in a book I can't afford, I can get it from my library, or
get it from the big world-wide library of the web.

I find the buying and selling of information per se to be highly
distasteful: sure, buy and sell books because it's nice to have a bound
printed reference to work from, but don't try to lock up the ideas,
because information should be free (everyone gains from access to
information), and one way or another information will be free.

Notice that none of this is to say that authors shouldn't be
remunerated, and very well remunerated, for their work - just that the
old-fashioned publishing model is broken beyond repair in the
electronic age (at least for technical works - probably not for
fiction).

Also, personal use doesn't authorize you or others to share it
over the Internet - personal means you not half the world. The
copyright system is not broken... you probably talk about the
patent system being broken which is something different.

No, it's the copyright conditions that forbid converting it to another
medium (in this case electronic). Recording TV programs to VHS (or DVD
nowadays) is also generally illegal as it isn't expressly permitted by
copyright holders who routinely "reserve all rights" unless they're
explicitly granted, but thankfully a huge majority of people have the
common sense to realize that this is idiotic.

So if I shoot you I should be safe because you would die anyway
eventually and I would still get my goal accomplished (identical
result). Screw the law, it's broken...

The obvious difference being that shooting me has a negative side
effect (namely my immediate death itself), whereas my two routes to
getting printed copies of K&R on allocations have no bad side-effects.

Patents, again, not copyright. You're getting it wrong. It
doesn't play on Linux because there is no program under Linux to
run it, because the guys distributing software respect the law by
not using stuff they don't agree with. You don't seem to get that.

Yes, that's a patent issue. I'd hardly say they respect the law - more
fear it. I seem to recall my distro came with a program that when run
gave a message like "We can't legally distribute DeCSS for absurd legal
reasons. This program will download it from a server based somewhere
it's legal - do this at your own risk." Quite clearly they don't think
it's wrong for people to download DeCSS - they're just afraid of being
sued if they distribute it themselves.

 

[nfwavzrdvwl]

Kernighan & Ritchie *are* around today, and if they wanted their book

released under a permissive license they could do so.

That's extremely unlikely - almost always publishers require authors to
transfer copyright to them. It would be interesting to know what their
view of information sharing...

It's unlikely you'll get any help from people who make a living with
intellectual property, now that you've demonstrated your cavalier
attitude towards it.

....and "intellectual property" is though. Of course there's a school of
thought that says the term "IP" is an extremely unfortunate one:
http://www.gnu.org/philosophy/not-ipr.xhtml

 

[Richard Heathfield]

(e-mail address removed) said:

You seem to be under a misapprehension. Nothing is being stolen.

You seem to be under the misapprehension that we care about your
twisty-turny "I'm not dishonest, even though I'm breaking copyright law"
self-justification. A crook is a crook, whether the law calls it stealing
or copyright violation or whatever.

 

[Richard Bos]

You seem to be under a misapprehension. Nothing is being stolen.

No, _you_ seem to be under several misapprehensions.

First, top-posting is _not_ acceptable except on junk newsgroups.

Second, it doesn't matter whether you call it theft, piracy, or
liberating the oppressed electrons. You're still a freeloader.

Third, nobody likes a freeloader, and nobody wants to help you.

Richard

 

[Richard Bos]

I find the buying and selling of information per se to be highly
distasteful: sure, buy and sell books because it's nice to have a bound
printed reference to work from, but don't try to lock up the ideas,
because information should be free (everyone gains from access to
information), and one way or another information will be free.

You know, every time someone trots out this argument, I wonder whether
they'd be willing to put their SSN, bank account number, PIN codes,
passwords, date of birth, and mother's maiden name on a web page for
everybody to see. That's information, after all, and information must be
free.

Richard

 

[Nelu]

I think that's an excellent thing to do, and I happily buy books...
however, I don't have unlimited funds to buy books. When I need the
information in a book I can't afford, I can get it from my library, or
get it from the big world-wide library of the web.

I don't either, so until I could afford to buy K&R2 (which is
relatively recent), I borrowed it from the library. And, yes, I
waited for it, every time. (Even worse, when I really needed it I
couldn't find it anywhere). I found a website once advertising a
free K&R(1) pdf and I downloaded. I was told it was not legal and
I deleted it.

I find the buying and selling of information per se to be highly
distasteful: sure, buy and sell books because it's nice to have a bound
printed reference to work from, but don't try to lock up the ideas,
because information should be free (everyone gains from access to
information), and one way or another information will be free.

Tough luck. The law says you have to, in this case. Other people
find it distasteful when people use their work without paying for
it. The law is on their side for now.

Notice that none of this is to say that authors shouldn't be
remunerated, and very well remunerated, for their work - just that the
old-fashioned publishing model is broken beyond repair in the
electronic age (at least for technical works - probably not for
fiction).


No, it's the copyright conditions that forbid converting it to another
medium (in this case electronic). Recording TV programs to VHS (or DVD
nowadays) is also generally illegal as it isn't expressly permitted by
copyright holders who routinely "reserve all rights" unless they're
explicitly granted, but thankfully a huge majority of people have the
common sense to realize that this is idiotic.

Fight to change it if you don't like it. Yes, a huge majority of
people are switching to relative morality... That may not be the
best thing ever. In my opinion it's even worse than broken laws.
Also, if I don't share 'illegal' content, it's really difficult
for anyone to know what I do with my personal copy.

The obvious difference being that shooting me has a negative side
effect (namely my immediate death itself), whereas my two routes to
getting printed copies of K&R on allocations have no bad side-effects.

How can you tell? What are writers supposed to live on?
Concerts??? Who are you to tell them they can't make money on
their work? If they sell one book and that gets shared over the
Internet chances are they won't make too much. It's like abusing
them. If they want to do it differently that's fine.

Yes, that's a patent issue. I'd hardly say they respect the law - more
fear it. I seem to recall my distro came with a program that when run
gave a message like "We can't legally distribute DeCSS for absurd legal
reasons. This program will download it from a server based somewhere
it's legal - do this at your own risk." Quite clearly they don't think
it's wrong for people to download DeCSS - they're just afraid of being
sued if they distribute it themselves.

I didn't say they agree with it, I said that they respect it. A
lot of people respect the law out of fear. That's why not
everybody has the courage to shop-lift.

 

[nfwavzrdvwl]

I don't either, so until I could afford to buy K&R2 (which is
relatively recent), I borrowed it from the library. And, yes, I
waited for it, every time. (Even worse, when I really needed it I
couldn't find it anywhere). I found a website once advertising a
free K&R(1) pdf and I downloaded. I was told it was not legal and
I deleted it.

If that makes you sleep easier at night, then good for you!

Also, if I don't share 'illegal' content, it's really difficult
for anyone to know what I do with my personal copy.

Is that supposed to mean that you think it's OK to make a PDF of a book
you own for personal use as long as you don't share it? Even though
it's against the law?

How can you tell? What are writers supposed to live on?
Concerts??? Who are you to tell them they can't make money on
their work? If they sell one book and that gets shared over the
Internet chances are they won't make too much. It's like abusing
them. If they want to do it differently that's fine.

This sounds like a compelling argument for closing all the libraries in
the world with immediate effect.

I find it incredible that this sort of FUD is still being trotted out
from intelligent people. "Oh, no one can make money from free
software!" Try telling that to all the employees of the FSF and Red Hat
and Sourceforge and the hundreds of little companies that make free
software.

The idea that there's no way to make money as an author or publihser
other than by restricting distribution is now years and years out of
date - O'Reilly are a living, breathing case in point of a company
making it work right now.

Once again I say: of course authors should be very well remunerated for
the work they do. The main obstacle to that is the short-term greed and
vested interests of fat-cat publishers, not those who share information
for personal use.

 

[CBFalconer]

As far as I know they are accurate. Not the memalign portion,
which is nonsense as published (and so labelled).

Actually there is fairly good documentation in nmalloc.txh (which
is intended to be a component of a larger library documentation)
together with instructions in readme.txt for converting that to a
usable html documentation file.

 

[Nelu]

Is that supposed to mean that you think it's OK to make a PDF of a book
you own for personal use as long as you don't share it? Even though
it's against the law?

No. The point is that if you're doing something illegal you
should shut up unless you're prepared to suffer the consequences.

This sounds like a compelling argument for closing all the libraries in
the world with immediate effect.

The libraries are buying the books. They are not doing something
illegal. And because they buy the book you have free access to
information. Most of the libraries I know have free membership
and the others have a very low price for the membership that is
*not* used to restrict your access to the information. They obey
the law.

I find it incredible that this sort of FUD is still being trotted out
from intelligent people. "Oh, no one can make money from free
software!" Try telling that to all the employees of the FSF and Red Hat
and Sourceforge and the hundreds of little companies that make free
software.

I didn't say that you can't make money in other ways and I am a
supporter of open source software although I have to use
proprietary software from time to time because there may not be
good open source alternatives. At the same time I recognize the
fact that there are people that don't want to do things the same
way and the law allows them to do things differently. If you
don't like it stay away from their software and books.

The idea that there's no way to make money as an author or publihser
other than by restricting distribution is now years and years out of
date - O'Reilly are a living, breathing case in point of a company
making it work right now.

Good for them. Other people may not want to go the same route if
they think they can make more money in other ways that are legal.

Once again I say: of course authors should be very well remunerated for
the work they do. The main obstacle to that is the short-term greed and
vested interests of fat-cat publishers, not those who share information
for personal use.

Good. If you think the authors should be very well remunerated
for their work then go and buy K&R. Stealing it won't bring the
authors any money.

 

[Andrew Sidwell]

(e-mail address removed) wrote:

Fight to change it if you don't like it. Yes, a huge majority of
people are switching to relative morality... That may not be the
best thing ever. In my opinion it's even worse than broken laws.
Also, if I don't share 'illegal' content, it's really difficult
for anyone to know what I do with my personal copy.

I didn't say they agree with it, I said that they respect it. A
lot of people respect the law out of fear. That's why not
everybody has the courage to shop-lift.

You seem to be promoting the view that legality defines morality, or
that the two are somehow equal. Three examples to disprove this:

1. Recreational drug users of say, cannabis, feel what they do is
entirely moral. The law disagrees.
2. Others feel that the government making lots of money from sales of
something which kills many thousands every year (say, tobacco) is
immoral. The law disagrees.
3. Ripping a CD to your iPod so you can listen to it on the move is
generally considered a moral actions. UK law, at least, disagrees.


Andrew Sidwell

 

[Andrew Sidwell]

The libraries are buying the books. They are not doing something
illegal. And because they buy the book you have free access to
information.

I'm sorry, but where in the process of buying a book (to scan and upload
it as a PDF) is the book not bought?


Andrew Sidwell

 

[Nelu]

I'm sorry, but where in the process of buying a book (to scan and upload
it as a PDF) is the book not bought?

I guess the periods should have been commas. Sorry about that.

 

[Nelu]

You seem to be promoting the view that legality defines morality, or
that the two are somehow equal. Three examples to disprove this:

1. Recreational drug users of say, cannabis, feel what they do is
entirely moral. The law disagrees.

Other people may disagree as well.

2. Others feel that the government making lots of money from sales of
something which kills many thousands every year (say, tobacco) is
immoral. The law disagrees.

Smokers disagree, in general.

3. Ripping a CD to your iPod so you can listen to it on the move is
generally considered a moral actions. UK law, at least, disagrees.

Singers may disagree.

Shop-lifters may think that what they are doing is moral.
This is moral relativism. The law is a very slow follower of a
morality shared by the majority. Until the new majority manages
to make changes whatever you think is moral may break the law.
The law usually reflects a morality shared by the majority at
some point in time, not necessarily the present.

 

[Keith Thompson]

Another eventual improvement might be to separate out entirely all
allocations under, say, 16 or so bytes, and perform them from a
separate chunk. The purpose being to avoid the overhead of the
control field for small allocations. This is more complicated.

It seems to me that that could cause problems if the implementation
has to make assumptions about how much memory will be needed for small
allocations vs. large ones.

A more general approach might be to allocate large chunks on demand,
and provide small allocations from within those large chunks.

This is just off the top of my head; there may well be flaws in my
reasoning.

 

[Keith Thompson]

That's extremely unlikely - almost always publishers require authors to
transfer copyright to them. It would be interesting to know what their
view of information sharing...

Under that assumption (which is likely to be correct), Prentice Hall
owns the copyright, since Kernighan and Ritchie sold it to them -- as
they were perfectly entitled to do. If Prentice Hall wanted their
book released under a permissive license, they could do so. If
Kernighan and Ritchie wanted the book they wrote released under a
permissive license, they could have done so themselves rather than
selling it to Prentice Hall. They might still be able to make some
sort of deal with Prentice Hall to allow it, though the final decision
would be up to Prentice Hall. They have not chosen to do so.

...and "intellectual property" is though. Of course there's a school of
thought that says the term "IP" is an extremely unfortunate one:
http://www.gnu.org/philosophy/not-ipr.xhtml

Yes, there is. But I don't recall the FSF ever advocating violation
of existing copyrights. They would probably prefer that K&R had
released their book under a free license in the first place, but they
didn't choose to do so.

Kernighan and Ritchie happen to be highly respected individuals around
here; Mr. Ritchie even posts here every now and then. And even if
they weren't, it wouldn't make any difference. You are violating the
laws under which they make their living, and you are bragging about
it. We are not interested in your excuses. Don't expect any help
here in the future.

 

[Keith Thompson]

The idea that there's no way to make money as an author or publihser
other than by restricting distribution is now years and years out of
date - O'Reilly are a living, breathing case in point of a company
making it work right now.

[...]

What makes you think that mentioning O'Reilly helps your case?

O'Reilly sells books. If you were to download a PDF copy of an
O'Reilly book without their permission, you would be violating their
copyright.

They also provide *some* materials free of charge, and others over the
Internet *for money*.

Until recently, O'Reilly offered a "CD Bookshelf" series, packages of
several of their books in HTML format on a CD-ROM. They've stopped
doing this, supposedly because it made their books too easy to
redistribute without authorization. In other words, *I* can no longer
obtain these valuable publications because of the actions of people
like *you*.