|
Why don't you start with 'fail-proof' parameters?
For instance you may start copying from the origin (top-left) of the source image.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
The problem with my custom threadpool (fun activity, not commercial) is this:
I have, say 5 threads running, a global counter of how many pieces of work there are, and a work event which should be unsignaled (reset) when there is no work, and signaled (set) when there is work, because when there is no work, the threads simply wait on this event. I have two methods PushWork() and PopWork(). PushWork() increments the global counter by 1 using an interlocked operation, and checks "if I just incremented the global counter to 1, SetEvent()". PopWork() decrements the global counter by 1 using an interlocked operation, and checks "if I just decremented the global counter to 0, ResetEvent() and wait on the event".
The problem is a race condition. Imagine if the work queue is currently empty.
PushWork() gets called, and increments the counter to 1.
Then, PopWork() gets called and decrements the counter to 0.
PopWork(), running faster than PushWork() (for whatever reason) resets the event.
PushWork(), chugging along, then sets the event.
Now, we have a no more work in the queue, but the event is set, so the threads keep polling the queue for work. There is a similar problem for the other way around. Imagine if the work queue currently has one item.
PopWork() gets called, and decrements the counter to 0.
Then, PushWork() gets called and increments the counter to 1.
PushWork() sets the event.
PopWork() resets the event.
Now, there are work items in the queue, but the threads will stop running as soon as it hits the event.
The reason why this can occur is because modifying the counter and setting/resetting the event are not atomic. I could simply wrap both of these with a critical section, but I think the overhead is too big, since it means that for every piece of work, there are two EnterCriticalSection() calls and two LeaveCriticalSection() calls, one for each of push and pop. I've been trying to find a way to do this without locks. Does anyone have any ideas?
INFO: I use a combination of global work queues and local work queues (one per thread) as per modern threadpooling implementations with work-stealing queues. I do, however, have one global counter for all the work. I've entertained the idea of using different counters but don't see how that would solve my problem.
|
|
|
|
|
Cyrilix wrote: The reason why this can occur is because modifying the counter and setting/resetting the event are not atomic. I could simply wrap both of these with a critical section, but I think the overhead is too big, since it means that for every piece of work, there are two EnterCriticalSection() calls and two LeaveCriticalSection() calls, one for each of push and pop. I've been trying to find a way to do this without locks. Does anyone have any ideas?
1. Lock-free programming is *very* difficult - and I don't think can be done for your specific case of multiple, unconnected actions.
2. If the overhead of calling critical section is significant compared to amount of work being done in the thread, your work items are much too small.
You need to make your two actions atomic - the only way to do that is to serialize access to a combination of work queue and event, using a mutex or critical section.
A different way might be for the thing that's pushing the work to select the thread that's to do the work and, by having an event per thread, signal the selected thread to pick up a work item. If there are no waiting threads, do nothing. And when a thread enters a waiting state, it can look at the work queue before entering the waiting state and pick the next work item.
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
You need to make your two actions atomic - the only way to do that is to serialize access to a combination of work queue and event, using a mutex or critical section.
I sort of figured that might be the case.
If the overhead of calling critical section is significant compared to amount of work being done in the thread, your work items are much too small.
What I use for work items is something in the order of a hundred multiplications/divisions. So, for instance, say I want to multiply two square matrices matrices or equal size using the naive method, I split up the work so that each <column,row> entry of the resulting matrix is a single work item. If I have a 100x100 matrix multiplied by a 100x100 matrix, then that gives me 100 multiplications and 100 additions for each of 100x100 (10000) work items. This seems to really stress my threadpool implementation since the single-threaded version of this naive matrix multiplication is a lot faster, and it's definitely due to the overhead of my threadpool. I was thinking that a more efficient use of synchronization (if possible) might alleviate this problem, however, I haven't actually extensively profiled my program. What I do know, however, is that the vast majority of the time is being spent on queueing the work, rather than doing the actual work.
A different way might be for the thing that's pushing the work to select the thread that's to do the work and, by having an event per thread, signal the selected thread to pick up a work item. If there are no waiting threads, do nothing. And when a thread enters a waiting state, it can look at the work queue before entering the waiting state and pick the next work item.
OK, that's some food for thought. I'll think about this and see if I can implement something accordingly.
Thanks for your comments.
|
|
|
|
|
I was thinking with my suggested alternate solution that as you're using an event per thread, you could use a lock-free queue - there are plenty of implementations on the web if you Google for "lock free queue c++". It's a case of finding a trust-worthy one! This[^] may be useful, while this[^] may be of interest, as might this[^]. In fact, as all of those are by Herb Sutter, Herb Sutter's blog[^] is probably of interest!
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
Cyrilix wrote: The reason why this can occur is because modifying the counter and setting/resetting the event are not atomic.
Have you considered using Interlocked Singly Linked Lists[^] for your work que? This would make adding, removing and querying all atomic operations.
Using Singly Linked Lists[^]
Best Wishes,
-David Delaune
|
|
|
|
|
I've seen that series of documents, although I haven't considered it for my implementation, though I don't think it really solves the problem I have of trying to make "push/pop and signal" atomic.
It does however seem like it would have better performance than the standard locked queue.
Thanks for bringing it up.
|
|
|
|
|
Hi all. I want to create a desktop application "Web-Filter" that can block unwanted websites. That can block website having Porn, Drugs, Crime related content. That can block Advertisement/Banners and pop ups. That can block chatting. I don't know where to start even. Don't know the best library for this stuff. But I know C++. Can somebody help me please? Please guide me how can I make such an application.
|
|
|
|
|
|
I have a fairly simple program that includes WYSIWYG text boxes to print worksheets for elemntary students. I am looking for a way to draw/print graphics borders around these boxes.
Is there a general class or a good way to load different graphics files and display them around the text as borders? For example, loading a file, and duplicating it around the box.
This is a C++ MFC Multidocument windows progam, something like Notepad but more advanced display printing. Any help would be appreciated.
|
|
|
|
|
Why didn't you use HTML?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
This is an older progam  that we are updating.
HTML isn't really an option.
|
|
|
|
|
Hi,
I need a little bit of clarification when a Thread is stared in a Worker thread
where there is a user fuction routine the Fuction and CWinthread are part of different
threads So....
if I have CSingleLocck object as a member of Cwinthread and try to pass it via m_pThreadParams
I might get a Access violation as the CSingleLock and threafunction are executing in different thread
context
Where as the RUNTIME_CLASS thread the CWinthread and all its meembers/overridables
::run, ::ininstance and other I care to define all Live in the same thread
|
|
|
|
|
|
I create CSingleLock in the thread
Obviously not a good idea the pass the object to a different thread
|
|
|
|
|
I'm very new to C and I've been working so hard on this and I have no idea what is wrong with it, I think it is in the Move method, but I wasn't sure so I included the whole program, if anyone can figure out why whats wrong please let me know! Thanks!
My assignment is to get through a maze that can be up to 50 by 50, the sample maze I've been using looks like this: The 1s are walls and the 0s are where you can step.
1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 0 0 0 0 1
1 1 0 0 0 1 0 1 0 1
1 0 0 1 1 1 0 1 0 1
1 0 1 1 0 0 1 1 1 1
1 1 1 0 1 1 0 0 1 1
1 1 0 1 1 0 1 0 0 0 S
1 0 0 0 0 0 0 1 0 1
1 0 1 0 0 0 0 0 0 1
1 0 0 1 0 0 1 1 1 1
1 0 1 0 0 1 0 0 1 1
1 1 1 1 0 1 1 1 1 1
E
It prints X's on the places it has visited and it will go left, but it won't go up, down, or right. it starts at S and ends at E, but it will only go over the first 3 0s, replace them with X's, remove the last two X's and terminate. Please help!
#include <stdio.h>
#define M 50
#define N 50
int rows, columns, exitRow, exitCol, enterRow, enterCol;
void printArray(char a[M][N], int rows, int columns);
int moveLeft(int currCol, int currRow, char a[M][N]);
int moveRight(int currCol, int currRow, char a[M][N]);
int moveUp(int currRow, int currCol, char a[M][N]);
int moveDown(int currRow, int currCol, char a[M][N]);
int Move(int currCol, int currRow, char array[M][N], int first);
void removeX(int currRow, int currCol, char array[M][N]);
int fail=0;
main()
{
char comma;
char foundEnter='n';
char foundExit='n';
int first=1;
//takes in the size of the maze
printf("Please type in the size of the field as rows, columns\n");
scanf("%d", &rows);
scanf("%c", &comma);
scanf("%d", &columns);
/*Asks user for input file and adds the field from the file to an array*/
char array[M][N]={9};
FILE *fptr;
char c;
char file_name[20];
int i,j;
printf("Type in the name of the file containing the Field\n");
scanf("%s",file_name);
fptr=fopen(file_name,"r");
for (i=0; i<rows; i++)
for (j=0; j<columns; j++){
c=fgetc(fptr);
while ( !((c == '1')||(c =='0')) ) c=fgetc(fptr);
array[i][j]=c;
}
fclose(fptr);
//Copies maze into the failed array
char failArray[M][N]={9};
for (i=0; i<rows; i++)
for (j=0; j<columns; j++){
failArray[i][j]=array[i][j];
}
//finds the entrance and exit of the maze
for(j=0; j<columns; j++){
if(array[0][j] != '1' && array[0][j]=='0'){
if(foundEnter=='n'){
enterCol= j;
enterRow=0;
foundEnter='y';
}
else{ exitCol= j;
exitRow=0;
foundExit='y';
}
}
}
for(i=0; i<rows; i++){
if(array[i][columns-1] != '1' && array[i][columns-1]=='0'){
if(foundEnter=='n'){
enterCol= columns-1;
enterRow=i;
foundEnter='y';
}
else { exitCol= columns-1;
exitRow=i;
foundExit='y';
}
}
}
for(j=columns-1; j>=0; j--){
if(array[rows-1][j] != '1' && array[rows-1][j]=='0'){
if(foundEnter=='n'){
enterCol= j;
enterRow=rows-1;
foundEnter='y';
}
else { exitCol= j;
exitRow=rows-1;
foundExit='y';
}
}
}
for(i=rows-1; i>=0; i--){
if(array[i][0] !='1' && array[i][0]=='0'){
if(foundEnter=='n'){
enterCol= 0;
enterRow=i;
foundEnter='y';
}
else { exitCol= 0;
exitRow=i;
foundExit='y';
}
}
}
//prints the array
printArray(array, rows, columns);
int currRow=enterRow; //sets the current Row to the enter Row
int currCol=enterCol; //sets the current Column to the enter Column
int end;
end=Move(currCol, currRow, array, first);
//if theres no path found it prints the fail array
if(end){
printArray(failArray, rows, columns);
printf("Path not found.\n");
}
else{
//if the path is found it prints the path to the exit
printArray(array, rows, columns);
printf("Path found.\n");
}
return 0;
}
//prints the array
void printArray(char a[M][N], int rows, int columns){
int i, j;
for (i=0; i<rows; i++)
for (j=0; j<columns; j++) {
if (j == 0) printf("\n");
printf("%c ",a[i][j]);
}
printf("\n");
}
//checks if move Left is possible
int moveLeft(int currCol, int currRow, char a[M][N]){
if(currCol-1>=-1)
if(a[currRow][currCol-1]=='0')
return 1;
return 0;
}
//checks if move Right is possible
int moveRight(int currCol, int currRow, char a[M][N]){
if(currCol+1<currCol)
if(a[currRow][currCol+1]=='0')
return 1;
return 0;
}
//checks if move Up is possible
int moveUp(int currRow, int currCol, char a[M][N]){
if(currRow-1>-1)
if(a[currRow-1][currCol]=='0')
return 1;
return 0;
}
//checks if move Down is possible
int moveDown(int currRow, int currCol, char a[M][N]){
if(currRow+1<currRow)
if(a[currRow+1][currCol]=='0')
return 1;
return 0;
}
//moves through the maze
int Move(int currCol, int currRow, char array[M][N], int first){
int fail;
int c;
array[currRow][currCol]='X';
failArray[currRow][currCol]='X';
//checks the exit condition as long as its not the first time through
if(!first){
if(currRow==exitRow && currCol==exitCol)
return 0;
if(currRow==enterRow && currCol==enterCol)
return 1;
}
//this is to track the array (temporary until code fixed)
first=0;
printArray(array, rows, columns);
printf("At Point row %d and col %d \n",currRow, currCol);
printf("fail=%d \n", fail);
getchar();
//goes left until it can't
if(moveLeft(currCol, currRow, array)){
c=--currCol;
printf("Moved left \n");
printf("Moving to col %d \n",c);
fail = !Move(c, currRow, array, first);
}
//if left fails goes up until it can't
if(moveUp(currCol, currRow, array) && fail){
c=--currRow;
printf("Moved up \n");
fail = !Move(currCol, c, array, first);
}
//if up fails goes down until it can't
if(moveDown(currCol, currRow, array) && fail){
c=++currRow;
printf("Moved down \n");
fail = !Move(currCol, c, array, first);
}
//if down fails goes right until it can't
if(moveRight(currCol, currRow, array) && fail){
c=++currCol;
printf("Moved right \n");
fail = !Move(c, currRow, array, first);
}
//removes the X so we can backtrack
removeX(currRow, currCol, array);
return 1;
//absolute failure
printf("Failed all \n");
return 0;
}
//removes the X and replaces it with a 0.
void removeX(int currRow, int currCol, char array[M][N]){
array[currRow][currCol]='0';
}
|
|
|
|
|
You're very unlikely to get an answer to such posts as it is very long and people here may not have the time to look at it.
You should read Chris' message How to get an answer to your question[^]
Finally, I think you should use a debugger and single step through your code.
And it would help if your code is properly indented.
«_Superman_»
I love work. It gives me something to do between weekends.
|
|
|
|
|
forensicgeek wrote: I wasn't sure so I included the whole program...
First mistake is there's never a reason to include so much code.
forensicgeek wrote: ...if anyone can figure out why whats wrong please let me know!
Second mistake is asking others to wade through all of this code. It's your assignment, after all.
Third mistake is that you did not read (or did but chose to ignore) this, especially point #7.
Rather than just run the program and hope it spits out the correct answer at the end, consider stepping through it using the ever-helpful debugger. You may not find the exact problem with it, but you can very easily narrow it down to just a small handful of lines rather than a whole program.
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
You can get through any maze by putting your right hand on the wall as you enter, then keeping your right hand on the wall as you walk through the maze.
I.e., whenever you have the opportunity to turn right, do it, still keeping your right hand on the wall.
When you reach a dead end, you loop around, still keeping your right hand on the wall at all times.
This will get through any maze. Another name for this search pattern is a Depth-First Search (http://en.wikipedia.org/wiki/Depth-first_search[^]).
|
|
|
|
|
Is there any way to get the time as represented on another computer on a LAN.
Regards,
Bram van Kampen
|
|
|
|
|
Use NetRemoteTOD().
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
Thanks,
Works a Treat. Blessed are those that remember all those Windows API Names.
Regards,
![Rose | [Rose]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/rose.gif)
Bram van Kampen
|
|
|
|
|
Hi,
I'm going to write small app ( in C++) for creating music, which would work under Win Xp, and I need some means for playing samples and streaming raw audio data.
I've looked up for some audio apis but I have no idea which one would be the best to perform this task. I've found some info about core audio APIs and I think that they would be right choose for my app. Unfortunately, as I know, they are just available for Vista and probably Win 7. That's why I would be grateful if you could give me some alternatives for this API (It also can be some cross-platform API).
Thanks in advance for help.
modified on Friday, September 18, 2009 3:06 PM
|
|
|
|
|
|
Thanks for that, but I forgot to mantion that I want to write in C++ rather than C. So I would need some c++ API.
Heh, I've just realised that ASIO is an API. So, thank you one more time for help.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
