LinuxQuestions.org
View the Most Wanted LQ Wiki articles.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 01-20-2011, 06:55 AM   #1
cin_
Member
 
Registered: Dec 2010
Posts: 266

Rep: Reputation: 23
C :: Using priorities and malloc() :: Designate Resource Consumption


I have a program, written in C, that runs different variables through a formula.
All of the input is logged into a massive file, and the program reads the file one line at a time, and plugs the values into the formula.

The issue is that the values grow exponentially with fifty thousand unique combinations and so to run the program is quite taxing for my memory and CPU...

The question is this:
Is there a way to allocate a minimum'maximum amount of memory'CPU that the program can use?

I am familiar with variable memory allocation, but I have never thought of it from a full program standpoint, and I have looked for literature that could explain but without result...
So often the goal of making good code great is speeding it up. In this case I want the opposite. I am fine if the program takes three weeks to finish under the throttled settings where it may have taken four days normally.

Again, is there anyway to control the amount of memory a program is allowed to use without the program terminating?
Causing the process completion time to an excess is quite alright.

Last edited by cin_; 01-21-2011 at 10:52 PM. Reason: gramm'err
 
Old 01-20-2011, 11:20 AM   #2
Snark1994
Senior Member
 
Registered: Sep 2010
Location: Wales, UK
Distribution: Arch
Posts: 1,632
Blog Entries: 3

Rep: Reputation: 345Reputation: 345Reputation: 345Reputation: 345
Quote:
Originally Posted by cin_ View Post
So often the goal of making good code great is speeding it up. In this case I want the opposite. I am fine if the program takes three weeks to finish under the throttled settings where it may have taken four days normally.
This is called a time/memory tradeoff


Quote:
Originally Posted by cin_ View Post
I have a program, written in C, that runs different variables through a formula.
All of the input is logged into a massive file, and the program reads the file one line at a time, and plugs the values into the formula.

The issue is that the values grow exponentially with fifty thousand unique combinations and so to run the program is quite taxing for my memory and CPU...

The question is this:
Is there a way to allocate a minimum'maximum amount of memory'CPU that the program can use?
I'm not aware of such a way - I feel you will get better results from using a better algorithm rather than trying to limit memory usage. For example, if the formula be changed to work like follows:
Code:
RESULT := 0
while read line into VALUE
    RESULT := function(RESULT,VALUE)
then you would reduce your memory usage to just two variables, RESULT and VALUE, plus whatever the function needs internally. You talk about exponential growth and combinations - what is it that you're actually trying to do?
 
1 members found this post helpful.
Old 01-20-2011, 01:27 PM   #3
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,395
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
If your program is started from a bash shell, there are limits that can/will be inherited from 'ulimit' settings:
Code:
              -c     The maximum size of core files created
              -d     The maximum size of a process’s data segment
              -f     The maximum size of files created by the shell
              -l     The maximum size that may be locked into memory
              -m     The maximum resident set size (has no effect on Linux)
              -n     The maximum number of open file descriptors (most systems do not allow  this
                     value to be set)
              -s     The maximum stack size
              -t     The maximum amount of cpu time in seconds
              -u     The maximum number of processes available to a single user
              -v     The maximum amount of virtual memory available to the shell
The problem that may follow from applying these limits is how a program behaves once a limit has been reached. At least three possible scenarios come to mind: the program behaves as if resources are inexhaustible and ignores resource depletion (crashes), the program recognizes resource depletion and shuts down gracefully (doesn't crash but doesn't finish), or the program uses special means to work within the limited resources (finishes). The latter is obviously your ideal, but probably requires extremely defensive programming, and also novel ways to limit conventional resource consumption. The amount of effort it would take to craft such a program is probably very high. I would recommend studying whether that cost is worthwhile to you, or whether simply throwing more resources at the problem is more cost-effective (and how cost is defined is completely up to you).

--- rod.

Last edited by theNbomr; 01-20-2011 at 01:29 PM.
 
1 members found this post helpful.
Old 01-20-2011, 01:48 PM   #4
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,125

Rep: Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119
Quote:
Originally Posted by cin_ View Post
to run the program is quite taxing for my memory and CPU...
So what? That doesn't quite make your problem or objective clear.

My guess is that you want to improve the responsiveness of other processes that are running at the same time as the big process. But I'm not sure. If that is your real objective, you should say so.

If that isn't your real objective, you need to explain a lot more about your objective.

Quote:
Is there a way to allocate a minimum'maximum amount of memory'CPU that the program can use?
Do you mean physical memory or virtual memory?

I expect you would mean physical if you understand the difference. But I think Linux does not normally support limits on per process physical memory.

As for CPU time, I don't understand why there should be any problem. Give that task a worse priority and it will get less CPU share.

The real problem for physical memory is there is no good priority system to limit a process's share of physical memory.

Quote:
I am fine if the program takes three weeks to finish under the throttled settings where it may have taken four days normally.
That is understandable.

Quote:
is there anyway to control the amount of memory a program is allowed to use without the program terminating?
I think I misunderstood that sentence on first read. Now I'm not quite sure.

I think you mean: Limit the physical ram for that process, but in a way that causes that process to use swap space instead of physical ram, so that when it wants too much memory, it will run slower but not fail.

I think you don't mean: Limit the physical ram for that process, causing it to terminate if it asks for more than that.

In other words, does "without terminating" modify "allowed to use" or does it modify "anyway to control".

Quote:
Originally Posted by theNbomr View Post
-m The maximum resident set size (has no effect on Linux)
That is exactly what I think the OP wants to control. To bad you can't.

Quote:
At least three possible scenarios come to mind: the program behaves as if resources are inexhaustible and ignores resource depletion (crashes),
I would assume that scenario.

Quote:
the program uses special means to work within the limited resources (finishes).
Possible in theory. But I think we can ignore that possibility for the current situation.

cin_, have you tried adjusting just the CPU priority? What was wrong with the results of doing that?

If a high priority and low priority process are both running, the high priority process gets the major share of CPU time as long as it has enough physical ram to run and it gets priority over physical ram as long as it uses the CPU time. In many cases, that is enough for CPU priority to effectively control ram priority.

That still makes paused high priority tasks slow to get up to speed again after whatever they were waiting for has happened. But that might be just an annoyance rather than a bad enough problem to need to be fixed.

There are some pathological cases that act the other way. The low priority task uses enough ram to ram starve the high priority task, so the CPU priority setting has no effect and the low priority task gets almost all the CPU time. Those cases are harder to fix.

There is one thing I would try if it were my problem. I don't know how to know whether this would work short of trying it:
First (and hardest) replace the malloc function inside the problem program with a version that doesn't use anonymous memory, but instead maps a giant temp file into its address space and allocates memory from there.
Second adjust the swapiness parameter of Linux to very low. I think that gives anonymous memory priority over file mapped memory.

Last edited by johnsfine; 01-20-2011 at 02:04 PM.
 
1 members found this post helpful.
Old 01-21-2011, 10:33 PM   #5
cin_
Member
 
Registered: Dec 2010
Posts: 266

Original Poster
Rep: Reputation: 23
All good stuff, thanks. I refined the memory allocation and added a priority setting.

Snark1994,
Were you trying to encourage through subterfuge that perhaps PASCAL would be better suited for such an effort? Or simply that this seems a rather Blaise'et effort?

theNbomr,
I think I will take some time to look into using screen() and this feature you pointed out to have a different user logged on running my program under some strict controls.

johnsfine,
Thanks for the thorough reply.
Your priority suggestion was essential.
I modified the priority using renice()... then I wanted to do it within the program itself so I looked into a usable library. I found <sys/resource.h> and <sched.h>.



pour postérité...
Example using <sys/resource.h>
First terminal...
Code:
# ./priorset
stage : 1 : from function : 7505 old priority : 0 :
stage : 1 : direct : 7505 old priority : 0 :
17
stage : 2 : from function :7505 new priority: 17 :
stage : 2 : direct : 7505 new priority: 17 :
17
stage : 3 : from function : 7505 back to: 0 :
stage : 3 : direct : 7505 back to: 0 :
17
#
...from a second terminal...
Code:
# ps -o pid,comm,pri -C priorset
  PID COMMAND         PRI
 7505 priorset         19
# ps -o pid,comm,pri -C priorset
  PID COMMAND         PRI
 7505 priorset          2
# ps -o pid,comm,pri -C priorset
  PID COMMAND         PRI
 7505 priorset         19
# ps -o pid,comm,pri -C priorset
  PID COMMAND         PRI
#

/src
Code:
//scanf(), printf()
#include <stdio.h>
//setpriority(), getpriority(), 
//CONST VARIABLES: PRIO_PROCESS : identifies second argument as a PID number 
#include <sys/resource.h>
main ()
{
	int my_pid = 0;  //0 for 'calling process'... the process of this program...
	int curr_proc = PRIO_PROCESS;
	
	int orig, 
            old_priority, 
            new_priority, 
            to_set = 17;
	
	int first, second, third; //psuedo-pause to run ps() and check priority, any integer value will cause to  continue
	
int pid;
pid = getpid();

	orig = getpriority(curr_proc, my_pid);
	printf("stage : 1 : from function : %d old priority : %d :\n", pid, getpriority(PRIO_PROCESS, 0));
	printf("stage : 1 : direct : %d old priority : %d :\n", pid, orig);
	scanf("%d", &first);

	setpriority(curr_proc, my_pid, to_set);
	new_priority = getpriority(PRIO_PROCESS, my_pid);
	printf("stage : 2 : from function :%d new priority: %d :\n", pid, getpriority(PRIO_PROCESS, 0));
	printf("stage : 2 : direct : %d new priority: %d :\n", pid, new_priority);
	scanf("%d", &second);

	setpriority(curr_proc, my_pid, orig);	
	old_priority = getpriority(curr_proc, my_pid);
	printf("stage : 3 : from function : %d back to: %d :\n", getpid(), getpriority(PRIO_PROCESS, 0));
	printf("stage : 3 : direct : %d back to: %d :\n", getpid(), old_priority);
	scanf("%d", &third);

return 0;
}
Thanks again for all of the good ideas.

Last edited by cin_; 01-21-2011 at 10:43 PM. Reason: gramm'err
 
Old 01-22-2011, 02:56 AM   #6
cin_
Member
 
Registered: Dec 2010
Posts: 266

Original Poster
Rep: Reputation: 23
top'd

I ran my program, and then, to test, I ran the Xine media player. The video was choppy, and lagged behind the sound, but the sound was unaffected.

Here is what top said...
Code:
# top -p 12625,7505

top - 23:46:41 up 1 day,  3:11,  4 users,  load average: 2.72, 2.33, 1.84
Tasks:   2 total,   1 running,   1 sleeping,   0 stopped,   0 zombie
Cpu(s): 55.1%us,  7.0%sy, 37.8%ni,  0.0%id,  0.0%wa,  0.2%hi,  0.0%si,  0.0%st
Mem:   1015508k total,   989816k used,    25692k free,   193744k buffers
Swap:  1004020k total,      300k used,  1003720k free,   468920k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND            
12625 root      20   0  263m  86m  26m S  108  8.7   6:16.78 xine               
 7505 root      38  18 10792 9252 1116 R   84  0.9  65:37.29 MY_PROG
# ps -eo pid,pri,comm | grep MY_PROG       
 7505   1 MY_PROG
# ps -eo pid,pri,comm | grep xine
12625  39 xine
#
...look at %CPU, they add to well over 100%.

The hope was to lower the resource consumption, mainly now the CPU% so other processes could run unaffected. This is still not happening even with my manual priority setting.
Are these the results that are expected from the work I did? Anything amiss? Any ideas?

How can I lower the %CPU for MY_PROG?

Last edited by cin_; 01-22-2011 at 03:23 AM. Reason: gramm'err
 
Old 01-22-2011, 04:52 AM   #7
Snark1994
Senior Member
 
Registered: Sep 2010
Location: Wales, UK
Distribution: Arch
Posts: 1,632
Blog Entries: 3

Rep: Reputation: 345Reputation: 345Reputation: 345Reputation: 345
Quote:
Originally Posted by cin_ View Post
Snark1994,
Were you trying to encourage through subterfuge that perhaps PASCAL would be better suited for such an effort? Or simply that this seems a rather Blaise'et effort?
Not at all... I'm afraid I don't even know PASCAL I just remember many times bashing away at a problem trying to chip little time savings (or in your case, memory) off a programme, when I would have been far better served by sitting back and thinking about the problem for a minute or two. There are some truly amazing books on algorithm design (Programming Pearls + More Programming Pearls, Jon Bentley; Introduction to Algorithms: A creative approach, Udi Mander) which really highlight this. So I was just encouraging you to make sure you were going about the problem the right way however, if the other suggestions are working for you, then there's no particular reason to change approach now...
 
Old 01-22-2011, 09:56 AM   #8
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,125

Rep: Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119
Your output from top contradicts (at least my understanding of) the most important aspect of your original question.

If I'm reading that correctly, MY_PROG had used 65 minutes of CPU time at that point, but had no significant use of memory.

Quote:
Originally Posted by cin_ View Post
I ran my program, and then, to test, I ran the Xine media player. The video was choppy, and lagged behind the sound, but the sound was unaffected.
It looks like MY_PROG should have had near zero impact on Xine. Did you compare to Xine running alone?

Quote:
look at %CPU, they add to well over 100%.
Each of those represents % of one logical processor.

I expect you have a dual core CPU providing two logical processors.

I expect Xine is mostly single threaded, so after using all of one logical processor, it can't make much use of the second, even if nothing else is running.

Since it is worse priority, MY_PROG probably just gets the portion of the second processor that Xine can't use anyway.

In a dual core CPU, using the rest of the capacity of the second core in this situation will slow down the first by a very small amount. So running MY_PROG should have some impact on Xine performance, but very little.

But do you instead have an older single core CPU in which hyperthreading provides the second logical processor? Using the second logical processor of hyperthreading takes away nearly half the performance of the first.

Quote:
The hope was to lower the resource consumption, mainly now the CPU% so other processes could run unaffected. This is still not happening even with my manual priority setting.
If that problem is hyperthreading, that is much harder to work around effectively. But I expect you have a newer CPU and dual core, not hyperthreading.

So what explains your results? My two best guesses are:

1) You haven't compared carefully enough (Xine with/without MY_PROG) and MY_PROG really doesn't make much difference to Xine.

2) You need a bigger difference in priority.
 
Old 01-22-2011, 01:46 PM   #9
cin_
Member
 
Registered: Dec 2010
Posts: 266

Original Poster
Rep: Reputation: 23
Do I contradict myself?
Very well then . . . . I contradict myself;
I am large . . . . I contain multitudes.
.WaltWhitman,1855edLeavesOfGrass

If you mean in how it pertains to MY_PROG's pri being lower, meaning it has a higher priority, then it is true I was attempting to create a situation opposite my intention.
Quote:
A numerically low value implies a high priority level. For example, a process with a priority of 5 has a lower priority than a process with a priority of 0. Similarly, a system process with a priority of -5 has a lower priority than a process with a priority of -15
!! I reran the tests. This time with Xine at 0 pri, and MY_PROG at 39 pri, and the top results simply swapped:Xine 8*%, MY_PROG 10*%; and Xine performance was far worse. I feel there is something I am not understanding...

As per the cores...

I am on an AcerAOD250 'handheld device'...
Code:
# cat /proc/cpuinfo
...
model name	: Intel(R) Atom(TM) CPU N270   @ 1.60GHz
stepping	: 2
cpu MHz		: 800.000
cache size	: 512 KB
physical id	: 0
siblings	: 2
core id		: 0
cpu cores	: 1
...
flags		: fpu vme de pse tsc msr pae mce 
cx8 apic sep mtrr pge mca cmov pat clflush dts acpi 
mmx fxsr sse sse2 ss ht tm pbe constant_tsc 
arch_perfmon pebs bts aperfmperf pni dtes64 monitor 
ds_cpl est tm2 ssse3 xtpr pdcm movbe lahf_lm

...
#
The Atom is a single core that supports hyperthreading... that is how I am running.

(i) Xine running alone gives the same 10*%, MY_PROG running alone gives 9*%.
(ii) The priority range is -20:20. renice() and sys/resource.h'setpriorty() follow these limitations. Regardless of my input the numbers will default to -20:20 if I try to exceed them. So, the greatest priority difference, for my kernel:2.6.33.4; is 0:39 for me as it defaults at 19.

Last edited by cin_; 01-22-2011 at 02:03 PM. Reason: gramm'err
 
Old 01-22-2011, 04:35 PM   #10
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,125

Rep: Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119
Quote:
Originally Posted by cin_ View Post
the program is quite taxing for my memory
Quote:
Originally Posted by cin_ View Post
Do I contradict myself?
...
If you mean in how it pertains to MY_PROG's pri being lower, meaning it has a higher priority
I meant that phrase about memory in the first post was contradicted by the info from top showing MY_PROG uses barely any memory at all.

I understood a higher "nice" number represented a lower actual priority, so I tried to avoid any confusion by always saying "worse" priority rather than lower/higher priority.

Quote:
I feel there is something I am not understanding...
I thought what I said earlier about hyperthreading would have explained it, once you added the info that you have hyperthreading enabled.

I don't know best how to work around the problem, just that hyperthreading appears to be the cause of the problem.

If it were really important to fix this problem, the only simple thing I can think of is disable hyperthreading (which usually is a BIOS setup choice).

If hyperthreading were disabled, the CPU priority would make a big difference. (So you would need to disable hyperthreading and get the priority right). I now understand that just getting the priority right does very little because of the interaction with hyperthreading. Just disabling hyperthreading without getting the priority right would make the Xine performance even worse.

Quote:
(i) Xine running alone gives the same 10*%, MY_PROG running alone gives 9*%.
That implies (as I explained earlier) that Xine is mostly single threaded. I'm sure MY_PROG is entirely single theaded.

Because Xine is mostly single threaded, it only ties up one logical processor. Thus, regardless of priority, it doesn't significantly reduce the use of the other logical processor by MY_PROG.

A solution an expert might use is (to leave hyperthreading enabled, but fix the performance problem in a better way):
Add a second thread to MY_PROG that, while MY_PROG's main thread is active, wakes up a few times per second and checks the load on the CPU. If the load is low (approximately just MY_PROG itself) that thread just sleeps a fraction of a second, then does t again. If the load is higher, that thread suspends itself and MY_PROG's main thread for a few seconds, then wakes up every few seconds to see if the CPU load is super light. Only after seeing the CPU load super light, unsuspend the main thread and go back to load checking a few times per second.

To figure out how to do all that, I would need to look up details on a bunch of different operations that I know are possible but don't know details. (In other words, at my own level of expertise, writing that code would require a bunch of research, not just slapping together the actual code).

Last edited by johnsfine; 01-22-2011 at 04:51 PM.
 
Old 01-22-2011, 05:36 PM   #11
cin_
Member
 
Registered: Dec 2010
Posts: 266

Original Poster
Rep: Reputation: 23
priority() priority one

Yeah, the memory tax was resolved quite easily actually, and the main focus became your suggestion of priority. I want both the CPU and MEM to have such fine results. It would be great if the program rested both values at'around'under 11%

As far as the second thread suggestion, I had used a sort of firemarshall function that checks the CPU load before a looping of the algo's operation, decides if it is a good time to let it run, pauses if the CPU exceeds a certain capacity, or allows it in if the CPU capacity can contain it.

But this looked like the code of the ignorant. As if I was constructing an elementary'bulky'clumsy solution for a problem where someone has puts years of development into creating an elegant library full of solutions. Perhaps this sort of desired result is more idiosyncratic than I thought. Perhaps this elegant library has yet to be created... by me.

Ignorant simply means you are unaware of knowledge, not that you contain none at all.
A perfect example of code of the ignorant:
Before my research produced the knowledge, simply enough as, of <sys/resource.h> library, and then later its implication'implementation, was when I used my knowledge of <sys/ioctl.h>, gathered from a previous project, in its stead.
I was using ioctl calls to send the renice() command, among some others for pid discovery, to the running pts.


This hyperthreading is the next ignorance to dilute.
Thanks; I always have more fun on the forums looking for questions than answers.

I will look more into this and post my results here, as always, pour postérité...

Last edited by cin_; 01-22-2011 at 10:18 PM. Reason: gramm'err
 
  


Reply

Tags
efficiency, malloc, memory, priority, resource


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
maximum memory usage of a program sancho1980 Linux - General 1 08-18-2009 04:01 AM
How to measure maximum memory usage of XYZ application? Grawp Linux - Software 1 02-21-2009 09:46 AM
malloc() memory corruption (C++) Coxynelle Programming 1 01-17-2007 05:07 PM
malloc() and system memory spaceman27 Programming 8 04-25-2005 10:58 AM
how to determine cpu usage, memory usage, I/O usage by a particular user logged on li rags2k Programming 4 08-21-2004 05:45 AM


All times are GMT -5. The time now is 11:33 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration