10000 split memory manager into "standard" malloc/free and gc by vitiral · Pull Request #1234 · micropython/micropython · GitHub
[go: up one dir, main page]

Skip to content

split memory manager into "standard" malloc/free and gc #1234

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 14 commits into from
Closed

split memory manager into "standard" malloc/free and gc #1234

wants to merge 14 commits into from

Conversation

vitiral
Copy link
Contributor
@vitiral vitiral commented May 6, 2015

Completes HALF of #1168

This pull request accomplishes the following:

  • split the memory manager into semi-standard malloc/free and garbage collector implementations
    • differences are the memory manager MUST provide a next, sizeof, valid and set_mark/clear_mark/get_mark interface. This is a valid requirement, as most micro memory managers I have seen have them (or it would be easy to add them) AND it saves significant space and time.

Still to do (should be pretty straightforward)

  • split up the allocation table into garbage collector and memory pool only attributes
  • make the info getting and dumping not dependent at all on gc.h

@vitiral
Copy link
Contributor Author
vitiral commented May 6, 2015

whew, @pfalcon @dpgeorge please take a look. That was a good amount of work, but pretty successful I would say!

@vitiral
Copy link
Contributor Author
vitiral commented May 6, 2015

Some comments:

  • The mem memory manager does all transactions through blocks, as this speeds up lookup (and makes things simpler) for several pieces of code (and is more compatible with tinymem, which returns an index).
  • BLOCK_FROM_PTR was left in gc.c because tinymem does NOT support this -- however when we implement pointer indirection I think we will be storing indexes (not pointers) inside of python objects, so BLOCK_FROM_PTR will just be redefined to pull the index out of the 32bit magic pointer.

Quick question:

  • gc_init requires the user to input a memory space to put the allocation table and pool. Is this necessary? Why couldn't this just be defined with some #defines and be implemented at compile time?

Once the code has been ready to review and is almost ready for a pull, I will do the final work of separating the structures and cleaning up the info/dump functions.

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

Well, now this is at least something. But immediate comment is that this is pretty obtrusive, so may take quite a while to review.

Some more comments:

split the memory manager into semi-standard malloc/free and garbage collector implementations

I'd say that this splits memory subsystem (gc.c) into memory manager and garbage collector running on top of it.

This is a valid requirement, as most micro memory managers I have seen have them

The causation is opposite here - memory manager should provide them, because gc requires them.

@pfalcon
8000
Copy link
Contributor
pfalcon commented May 6, 2015

gc_init requires

It should be clear that gc_init is not gc init, but memory manager init, and thus it is specific to a particular memory manager.

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

More comments:

On critical path to acceptance of this would be proof that this doesn't hurt performance of existing memmgr/gc implementation. Thus, having mem_sizeof() and friends as normal functions isn't good idea. Ideal performance form for them would be macros, as that guarantees inlinability in compiler-independent way. But that would be too cumbersome for human. Thus, they must be inline functions with a proof of inline (-Winline, assembly inspection).

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

On the other hand, you should prove that gc/memmgr interface is powerful enough to implement gc on top of malloc with minimal memory overhead, which is set as 2 words. (Please forget about tinymem, there's only existing memory manager and malloc authoritative usecases now).

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

mem.c is thus not mem.c, but something like mem_bitmapped_pool.c . The other implementation is mem_malloc.c . Maybe "memmngr_" prefix even would be more descriptive.

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

There're lot of issues with codestyle.

@vitiral
Copy link
Contributor Author
vitiral commented May 6, 2015

But immediate comment is that this is pretty obtrusive, so may take quite a while to review.

I think it is less intrusive if you just think of it this way: I moved all memory allocation/freeing to mem.c+h, while all garbage collection stayed in gc.c+h

I changed very little about how anything worked (besides adding a few features like next)

The causation is opposite here - memory manager should provide them, because gc requires them.

Haha, well yes, I suppose that is true.

you should prove that gc/memmgr interface is powerful enough to implement gc on top of malloc with minimal memory overhead, which is set as 2 words

Two words (32 bit uints I assume?) should be doable. It would be through a different memmgr function built on top of malloc/free.

[mem_sizeof, etc] must be inline functions with a proof of inline (-Winline, assembly inspection).

agreed

Maybe "memmngr_" prefix even would be more descriptive.

memmngr is a little wordy, how about memp (memory pool) or memt (memory table)?

There're lot of issues with codestyle.

I'm sure I can fix them easily enough. I'll take a look at the style guide and see if I can spot them tomorrow.

@vitiral
Copy link
Contributor Author
vitiral commented May 6, 2015

Also, it looks like it is failing compilation/tests on some of the embedded platforms. Any idea why that would be?

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

I changed very little about how anything worked (besides adding a few features like next)

Now prove that, if it's all green and red.

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

Also, it looks like it is failing compilation/tests on some of the embedded platforms. Any idea why that would be?

You wrote the code and you're asking that?

@vitiral
Copy link
Contributor Author
vitiral commented May 6, 2015

Now prove that, if it's all green and red.

Things moved files, which is why they were "deleted" from one file and "added" to the other. Git doesn't pick up these kinds of diffs.

This is a pretty major update, the whole point is that we completely remove a whole section of code from gc.

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

memmngr is a little wordy, how about memp (memory pool) or memt (memory table)?

It's not pool, it's not table. It's memory manager. But as memory manager manages memory, perhaps it's abbreviatable to just memory, i.e. "mem".

@vitiral
Copy link
Contributor Author
vitiral commented May 6, 2015

You wrote the code and you're asking that?

Never compiled anything on a STM32 or most of these other platforms, especially not something as large as the micropython library. I'm wondering if they don't define their own object files in their makefile? This is the only thing I can think of, as everything should have remained cross platform. (except that I added a file)

@pfalcon
Copy link
Contributor
pfalcon commented May 6, 2015

You do look at the actual failure(s), instead of guessing, right? https://travis-ci.org/micropython/micropython/builds/61521248#L1130

@vitiral
Copy link
Contributor Author
vitiral commented May 6, 2015

ah, there they are. Nevermind, I should be able to figure those out... (I've not used Travis before either)

…d mem_free instead of custom solution (and standard free deals with this)
@vitiral
Copy link
Contributor Author
vitiral commented May 7, 2015

I've almost separated the data structures now. Still some work to be done.

@vitiral
Copy link
Contributor Author
vitiral commented May 7, 2015

The major issue with separating the data structures is going to be how to initialize the memory pool. @pfalcon has suggested that gc_init is "specific to a certain memory manager", so we need a general way to deal with multiple memory managers.

How do you suggest we enable/disable certain memory managers? Very soon I will have the std malloc/free memory manager that can plug into gc and we will have to address this issue -- obviously (right now) linux should use standard malloc/free and embedded should use mem.

@vitiral
Copy link
Contributor Author
vitiral commented Jun 12, 2015

I would like to continue work on this if there is still interest. What needs to be done to merge this? Because the memory manager is split, there has to be some solution for separating how memory is allocated for memory manager vs. garbage collector -- primarily the finalizer table (as they are now separate). Either that or we have to require all memory managers we use to include a finalizer table, which would be acceptable to me at this point.

Thoughts? Based on @pfalcon's comments in #1279 there are other issues (because of splitting the files) but I am unsure of how else this should have been done and what the solution is now (complete rework that will end up in split files anyway?). Please comment.

@vitiral
Copy link
Contributor Author
vitiral commented Jun 12, 2015

I am willing to rework this one commit at a time all in the same file if that is what is necessary to get this pulled. It will actually be fairly trivial.

I would split it into the following PRs:

  • split functionality in the functions (except for init) into malloc/gc
  • split up the data structures, create new local data structures for only malloc
  • split up malloc with new implementation (see comment above)
  • Split the files, creating mem.*
  • add a linux malloc implementation to show how easy it is to do a "drop in allocator"

Each of these would be separate pull requests. Would this be acceptable?

@pfalcon
Copy link
Contributor
pfalcon commented Jun 12, 2015

if there is still interest

There's interest, thanks.

@pfalcon
Copy link
Contributor
pfalcon commented Jun 12, 2015

So, I tried to do quick comments soon after patchset was posted, and hoped that other participants would review later, but that didn't happen. @dpgeorge should really look into this and tell how it should be, and other suggestion are "forward-looking statements".

But otherwise, yes, rule of thumb is that changes should be:

  1. As small as possible
  2. While achieving the needed functionality

For big changes, the above is rather hard to achieve, and well, that's art of programming and contribution of big enough patches to big enough projects.

So yes, now that you have this draft patchset which shows where you want to arrive, I'd suggest leave it as is for reference, and submit localized changes PR by PR, each change should be small, and leave everything in a working state.

@pfalcon
Copy link
Contributor
pfalcon commented Jun 12, 2015

Or I can tell how I'd do it - I'd make minimal set of changes to make uPy run with either existing memory allocator or with malloc/free. That would be the aim, and any change should be subordinare to it. If there's possibility to achieve the aim without splitting or renaming something, that's the way to go (while obviously doing everything in a generic manner). Splits and renames can be left for later cosmetic phase.

@vitiral
Copy link
Contributor Author
vitiral commented Jun 12, 2015

awesome. #1320 is the beginning of my efforts. Is this about the right way to do things?

@pfalcon
Copy link
Contributor
pfalcon commented Jun 12, 2015

Is this about the right way to do things?

Simple question - simple answer: no, it is not. That patch is codedrop of 420 lines, every second having codestyle problems. Start with a (useful!) patch of 10 lines, get it right, that's my suggestion. Other reviewers may have different opinions.

@vitiral
Copy link
Contributor Author
vitiral commented Jun 12, 2015

10 changed lines of code is not going to split the memory manager. Decoupling gc_alloc requires a complete rewrite of the function, there is no other way to do it.

I could of course do this completely piecewise, adding in functions that are already written only as they are "needed." Is this what you want or are you asking me to start from complete scratch?

@pfalcon
Copy link
Contributor
pfalcon commented Jun 12, 2015

Ok, so if the above "how I'd do it" hints are not enough, let me be more specific:

  1. You introduce mem_sizeof() function. Your patch makes it look like you wrote it, but that's not the case, you just factored out existing code into a function. Those and only those operations should be content of the 1st patch.
  2. @dpgeorge will never merge that patch, because it jeopardizes performance of the product he offers. So, next thing you add "inline" to that function, and prove that it actually works - by looking at the generated assembly, by running extensive testsuite.
  3. Not only you should verify lack of regresses, everyone else should be able to. easily. So, you either should provide step by step instructions, or way to automate testing (preferrable, as all the above will need to be repeated 50-100 times).

Again, all the above is my personal opinion, and you can wait for other suggestions.

@vitiral
Copy link
Contributor Author
vitiral commented Jun 12, 2015

I see what you mean. This is incredibly frustrating, as all the functionality was basically done and this is a significant amount of extra busy work to get done. I'm slightly worried that I'm going to do 8 hrs+ of work and it is going to be rejected again :/

I'll try to do it the way you suggest, by doing small commits and then getting your feedback.

@pfalcon
Copy link
Contributor
pfalcon commented Jun 12, 2015

I find myself regularly in a position that my code is not merged, and I know how frustrating it is. Here, where I'm on the other side, being a maintainer, it's not less frustrating to see people doing a great work in not so right way, so their work is not directly mergeable without a lot of clean up on maintainers' side and leaps of faith.

That's why I did that rant in #1279 try to send clear message that if people implement something to be merged, then they should care that it's easily mergeable, otherwise queues are long in every open-source project (damn, it's not that different in commercial projects, just less visible to outside). Steps to produce mergeable changes are not rocket science and are obvious as soon as you start to think about them - they are essentially to capture each separate and standalone step you do, and then do the steps in a separate and standalone way, without intuitive leaps back and forth.

I'm slightly worried that I'm going to do 8 hrs+ of work and it is going to be rejected again :/

You're not going to do 8hrs on that. You will spend 10-15 min to prepare patch for single function, if it passes review, you will go on with few next. At no time you would be spending 8hrs on it (well, maybe, after both you and maintainers are sure that code you'd produce is mergeable).

I'll try to do it the way you suggest, by doing small commits and then getting your feedback.

Thanks. 1 commit, and getting full feedback. Then reusing that experience for next commits (few again).

@vitiral
Copy link
Contributor Author
vitiral commented Jun 12, 2015

@pfalcon I ended up doing the gc_sweep first, as it is a pretty simple use case of decoupling. Essentially two things have to be decoupled from the overall memory manager:

  1. stepping through all memory (done with mem_first and mem_next)
  2. freeing memory separately (done with mem_free)

It ended up being a few more lines than 10, but I think it should meet all your qualifications. I tried to not add functionality that was already implemented like you said and keep everything as a macro. There are also comments on how things might be able to be sped up a bit, but I will leave it to you to determine how important that is.

Thank you for taking the time to review my code and offer these tips. I would really like to be a core contributor to this project, and it is obvious that I need to learn the proper way to structure pull requests to do that.

Edit

The PR is #1321

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants
0