|
I'd prefer not to do buddy recombination on the fly, i.e. when allocating/deallocating a block. I want neither allocation nor deallocation to be delayed by block recombination.
If you run out of space for bigger blocks, the freelists for smaller blocks may be long. To find buddies fit for combination is similar to sorting the list. It would be inefficient to go to the first smaller list (below the requested size) for the search; it may have viable candidates, but one block's buddy may live as two not-yet-combined halves in the second smaller list. So recombination should start at the smallest unit, and proceed upwards.
This you can leave to a very low priority task. The task unhooks a freelist for a given size, possibly leaving a couple entries for other threads' requests while the combination is being done. The task sorts the unhooked freelist to make combinable buddies list neighbors. If the heap start address is a multiple of the largest block that can be allocated, an XOR between the neighbors' addresses leaves the single bit that is the block size being processed; that is super fast. The two are unlinked, and the lower put into a separate list. Forget the upper one from now on - it is merged into the lower. When reaching the end of the list, the task is left with two lists: The reduced one (of the size being processed) and a list of recombined next size blocks, to be added to that freelist.
At the start, the task must reserve one freelist head while unhooking; that is done in a couple of instructions. At the cleanup, it must again reserve the freelist head to hook the reduced list back in, and then add its entries to the next bigger freelist. Both operations are done in a couple of instructions. There is no hurry: Noone is hurt if the task must wait in line before getting to add its entry to the two list heads. The order doesn't matter; if one head is busy, it can do the other one while it waits.
The task processes one size at a time. Each size usually has a moderate size freelist, so the time spent doing the job is moderate. Doing a real list sort might be a good idea: With allocation done from the list head, after the combination, the lowest available block is allocated for the following requests. If a bigger buddy must be split, it will be the lowermost of those. This strategy tends to gather active heap blocks at lower addresses, leaving the higher addresses for larger blocks (without the risk of a few single small block allocations in the upper range 'polluting' a large heap area). A block release may be a block at a higher address, but at the next compaction, the sorting will move it further out it the freelist, reducing the chances of it being allocated anew.
For the sorting part: When the compaction task unlinks a freelist, ready to start the sorting, chances are that the last part of the list are the same entries as on the previous compaction. There are suitable list sorting algorithms of O(n) on a sorted list, so the cost is dominated by the number of new freelist entries - which is probably not very high, since those freed are the first to go out of the list again. If the list has no already sorted tail, it indicates that the list has been all empty in the meantime, and probably hasn't grown that big yet.
If you let this low priority recombination task iterate over available block sizes, from bottom up, you will maintain a distinct locality of the heap use, towards lower addresses. The iteration frequency may be self-tuning: If the task found no more than, say, two combinable buddy pairs in any list, it may increase its delay before the next iteration by 50%. If it found sixteen pairs or more in any list, it may half its delay.
Given a background task for recombining buddies, allocation can be done in a couple instruction from a non-empty freelist, adding a small handful of instructions for each level it must move upwards if the list is empty. Release is (always) done in a couple of instructions.
Obviously: If you really run out of heap space - even the freelist for the largest block size is empty - then the recombination task must be force activated to combine buddies from the smallest up to the biggest block size. If even that fails, then you are really out of heap. If it succeeds, take it as a hint that the task should be run at a higher frequency!
|
|
|
|
|
I do the splitting and recombining during allocations and deallocations. It's fairly efficient, and the code already has the heap mutex. A background task has to lock out users for longer. I just make all users share the cost, because I can't see how offloading the work to a background task can make things any more efficient.
|
|
|
|
|
It all depends on OS/hardware context. "Background" doesn't always mean a background task in the OS sense.
You can offer your applications a heap manager providing allocate/deallocate as intrinsics / inline functions working on freelists with operations synchronized on hardware reservation (available in several architectures), with need for software semaphores. That is all your applications see.
Behind the scenes, your heap manager can have a clock interrupt handler doing the recombination. Even if the clock handler must maintain a list of timed events (it probably has one already!), regular activation of a recombination task is magnitudes cheaper than using OS mechanisms to start a background process in the dotNet sense, or of most other OSes.
Your apps won't know the reason why memory is so tidy all the time. They will get the memory blocks they ask for, in a small handful of instructions; release goes in even less. Your apps are never delayed by any (lengthy?) recombination of buddies. The risk of heap pollution from small memory allocation blocking large recombinations is greatly reduced.
You do not provide details about your procedures: When deallocating, do you search for buddy blocks for recombination of the same size only, or do you recurse to larger blocks, possibly up to the maximum size available? Do you keep freelists sorted for efficient identification of buddies, or are they unsorted?
Corollary: On new allocations, will you allocate new blocks minimizing the pollution of the heap by small blocks preventing allocation of large blocks? This is more or less implicit with sorted freelists, but if your freelists are not sorted, how do you maintain it?
|
|
|
|
|
Most memory allocated at run-time is actually taken from object pools[^] allocated when the system initializes. Each pool supports a major framework class, and the number of blocks in each pool is engineered based on the system's object model.
The buddy heap[^] is seldom used at run-time. It is used to allocate byte buckets for IP message payloads or when using the framework to implement a standalone application. Most allocation occurs in the pools.
The buddy heap[^] has a queue for its block sizes (powers of 2). Allocation can recursively split a block, and deallocation can recursively merge blocks.
Both memory managers verify that a pointer references a valid block, support debug tools that can be enabled to trace activity, and collect usage statistics.
|
|
|
|
|
I do not use dynamic memory allocation on my systems. Anyway, most of my targets 'feature' 4 KB of SRAM, so malloc would be overkill.
I am interested in trying dynamic allocation on larger system (embedding Lua, for example, would require that), but never did before.
"In testa che avete, Signor di Ceprano?"
-- Rigoletto
|
|
|
|
|
For some reason I simply can't imagine calling malloc on a 4kB system. 
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
By default, the IDE (PSoC Creator) sets the heap size to 128 bytes.
"In testa che avete, Signor di Ceprano?"
-- Rigoletto
|
|
|
|
|
|
|
AFAIK there is no reflection in C++. You cannot have something like:
struct S{
int value;
double number;
}
S to_serialize{1, 3.14};
std::string tag;
stream strm;
for (auto& m: members_of(S))
{
strm << name_of(m) << ': ';
strm << to_serialize.m << std::endl;
} In a language with reflection this would produce an output like:
value: 1
number: 3.14
Mircea
|
|
|
|
|
Mircea Neacsu wrote: AFAIK there is no reflection in C++.
Ok? That of course makes sense given that the link I posted is a about a new feature that will be added to the next standard.
Kind of silly to add it if it already existed.
|
|
|
|
|
RTTI is the only metadata functionality I'm aware of in C++.
There are hacks to sort of divine some reflective type information at compile time like SFINAE but not at runtime excepting RTTI i think.
But then the only thing I really have worked with is C++17 and prior, so if they have introduced something besides since I wouldn't know.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
honey the codewitch wrote: RTTI
Yeah that is the one that I was remembering.
So then that is not sufficient perhaps? Limited in some way?
In Java/C# one can get to things like class name, method names (public and private), method parameters (types), access types, class attributes. All of those can be listed and manipulated.
So for example if a class attribute is private and modifying that is going to help with better unit testing one can write reflection code to modify it. That is the most common use I have used for accessing private attributes. I don't use it that much and seems like bit of a wash versus adding a setter/getter.
|
|
|
|
|
RTTI is extremely limited last time I checked. Given I've maybe used it once to play around with it years ago and that's it, so don't quote me. It's nothing like what .NET offers, for example.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
Ok. But a brief reading of the link I posted suggests that will changing.
|
|
|
|
|
Personally, I'd probably still avoid it unless it solved a very significant problem for me because I like being able to make 17KB dlls that are actually useful.
Metadata ain't free.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
honey the codewitch wrote: I'd probably still avoid it unless it solved a very significant problem
Specific times I have used it in other languages.
- Dynamic loading of classes. Especially when parameter lists are dynamic.
- Messing with private data of a class. Most the time for unit tests, but I think one time it was in the production code. In C++ there is a way to do that anyways but it always risky and just as hacky.
honey the codewitch wrote: Metadata ain't free.
Which is why it has taken so long I suspect.
|
|
|
|
|
I am asking a question about regular expression.
I am NOT looking for references to AI regular expression generators.
Here in my text to find matches of ALL "hci" in it:
"Devices:\n\thci1\t00:50:B6:80:4D:5D\n\thci0\t00:15:83:15:A2:CB\n"
Here is my attempt to accomplish that task
QRegularExpression re("(hci[0-9]+)");
It matches only first occurrence of hci1" and twice
Please follow the established CodeProject instruction and read the post.
PLEASE no references to AI regular expression generators.
I need to learn TO BUILD regular repression - specially how to write it so it will attempt to match multiple items.
PS I did try to use "global match" , no go.
|
|
|
|
|
Salvatore Terress wrote: Please follow the established CodeProject instruction and read the post.
PLEASE no references to AI regular expression generators.
Please stop giving us orders. You have already been kicked off this forum once for your bad attitude. Everyone who tries to answer questions here does it in their own time and at no cost to you. If the answer is not what you were hoping for then feel free to ignore it.
|
|
|
|
|
Why didn't you post the code?
I mean, you commented
But only the regular expression constructor is shown.
"In testa che avete, Signor di Ceprano?"
-- Rigoletto
|
|
|
|
|
Salvatore Terress wrote: It matches only first occurrence of hci1" and twice
Did you mean something like 'it only matches once but there are two'?
Salvatore Terress wrote: I need to learn TO BUILD regular repression
Your regular expression is correct.
So that means your usage of the regular expression engine/library is incorrect. Nothing to do with the regular expression itself
Typically an engine/library will have an iteration idiom where each loop matches the next one.
I didn't look at all but the following google seems to return results that would be relevant.
{code}
"QRegularExpression" iterate through matches
{code}
|
|
|
|
|
Since my last post is nowhere to be found here...
I do appreciate all help resolving the issue.
And since posting code was requested, here it is.
It generally works retrieving multiple matches...
such as "hci1 hci0 "
what is missing is to retrieve PAIR of matches
such as
"hci1 00:xx:yy...
in other words I can retrieve name or address but not BOTH.
I would be grateful if somebody can give me the actual code and explanation how to match PAIR of values.
As can be seen - I did try different placement of parentheses
" (...)" but it did not work.
{
text = " START MATCH NAME AND ADDRESS CODE BLOCK ";
textEditPtr_DEBUG->append(text);
#ifdef TASK
DELETED
#endif
QString word;
QStringList words;
QString pattern = "Devices:\n\thci1\t00:50:B6:80:4D:5D\n\thci0\t00:15:83:15:A2:CB\n";
QRegularExpression re("(([0-F]{2}[:]){5}[0-F]{2})");
QRegularExpressionMatchIterator i = re.globalMatch(pattern);
text = " HAS MATCH MULTI";
qDebug()<< text;
textEditPtr_DEBUG->append(text);
#ifdef BYPASS no go
foreach(auto item,i)
{
text = " TEST foreach ";
text += item;
qDebug()<< text;
textEditPtr_DEBUG->append(text);
}
#endif
while (i.hasNext()) {
QRegularExpressionMatch match = i.next();
word = match.captured(1);
words << word;
qDebug()<< word;
text = " Full match name and address... ";
text += word;
qDebug()<< text;
textEditPtr_DEBUG->append(text);
}
#ifdef BYPASS
else
{
text = " NO MATCH MULTI";
}
#endif
qDebug()<< text;
text = " END MATCH ADDRESS CODE BLOCK ";
textEditPtr_DEBUG->append(text);
}
|
|
|
|
|
Salvatore Terress wrote: Here in my text to find matches of ALL "hci" in it:
So based on your sub - reply to me
"Devices:\n\thci1\t00:50:B6:80:4D:5D\n\thci0\t00:15:83:15:A2:CB\n"
What you actually want is the following
hci 00:50:B6:80:4D:5D
hci 00:15:83:15:A2:CB
Your text sample represents a multi-line input presumably with tab separators.
From that sample it is actually pointless to use a regex since normal parsing (or csv parser would work.)
But in terms of Regex you have several problems
1. Dealing with multiple lines
2. Correctly matching the values.
3. Dealing with special characters (including perhaps #1 above.)
4. Dealing with a list of results - as I stated in my other reply.
So your regex is not even close to correct for matching the address.
Looking at 2 only because that is the part most likely to be usable as a regex the equivalent regex for Perl would look like the following. Since you are not using Perl yours might vary but I suspect not.
(hci\w+([a-fA-F0-9][a-fA-F0-9]:)+[a-fA-F0-9][a-fA-F0-9])
There are variations on the above
- Making the tab explicit
- Restricting the id to the exact length
- variation on the hex digit but I prefer the above form
|
|
|
|
|
Thanks, but it still does not do what I want, as you expected it may. .
Would it be OK to actually discuss and analyze this ?
I am asking I am NOT telling the group shoud do that.
QRegularExpression re("(hci\w+([a-fA-F0-9][a-fA-F0-9] +[a-fA-F0-9][a-fA-F0-9])");
There are , imho , important parts (to reg exp ) and they are ok when used alone.
1. If I opt to use QRegularExpressionMatchIterator i = re.globalMatch(pattern);
There should be at lest three "code groups " delimited by "(,,,code group... )"
2. there are TWO base "reg expressions " one working OK as is
"hci[0-9]" - function as "match hcix where x = [0-9] - some doc call [0-9] range
or
hci\w should perform SAME task
3. the analysis of "xx:" using [a-fA-F0-9] is simply "too cute " and [0-F] with "how many times do the previous - {2} works as well.
I have no need to check for lower case "hexadecimal " since that actually does not exist anyway...
So - I will , perhaps stubbornly, try to continue usage of at least ONE of the QT classes and maybe will
find correct modification of the above.
If i end up with plain "reg_exp" so be it...
Thanks
|
|
|
|
|
When you post code use code blocks.
Salvatore Terress wrote: If I opt to use QRegularExpressionMatchIterator i = re.globalMatch(pattern);
Not sure how to emphasize what I have already said several times.
That question is NOT about regular expressions.
It is about how to use that specific library.
I suggest you start with a less difficult example to figure out how iteration works. And google for examples as I documented in the other reply.
Salvatore Terress wrote: There should be at lest three "code groups " delimited by "(,,,code group... )"
You mean the parens. Parens are used for 'capturing' and for 'grouping'.
For the case I gave the inner ones was to group the outer for capturing.
And yes that is a problem when you iterate. The library you are using might have a way to specify that the parens are not 'capturing'.
In Perl it looks like the following. There would be only one capturing group which would match either 'abcxyz' or 'defxyz'.
((?:abc|def)xyz)
I will note that I use that feature so rarely that I had to look it up.
Salvatore Terress wrote: the analysis of "xx:"
As I mentioned there are variations to what I suggested. Myself I don't care for using '{2}' in a case like this. Just a preference.
(Had to edit the above because I messed up the code block)
modified 16-Nov-23 10:40am.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
