Kind of like what Warp talks about w.r.t. cache lines, except with VM pages.

http://queue.acm.org/detail.cfm?id=1814327

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Darren New wrote:
> Kind of like what Warp talks about w.r.t. cache lines, except with VM 
> pages.

It's all just different levels of the memory hierachy.

It used to be that you had a block of RAM, all accessible in O(1) time. 
Now you have virtual memory (which pretends to be RAM, but is orders of 
magnitude slower), maybe three levels of cache (which pretends to be 
RAM, but is orders of magnitude faster - except if it's another core's 
cache, in which case it's *slower* than RAM again due to coherance 
issues), and you could regard the CPU registers themselves as the 
ultimate level-0 "cache".

The sad fact is, processors are now 1000x faster than they used to be, 
but RAM is still roughly the same speed. And that means that if you 
don't want your expensive new CPU to just spend 1000x more cycles doing 
nothing, you need to have this memory hierachy. And *that* means that 
the time complexity of your algorithm is now *irrelevant*. The *only* 
thing that matters now is cache behaviour.

As the paper says, a stupid O(n^2) algorithm could be *faster* than a 
sophisticated algorithm with O(log n) or even O(1) time-complexity, all 
due to cache effects that shouldn't be there in the first place. Decades 
of research and development ruined. Now we have no way to predict 
performance, because it depends on cache behaviour, which intimately 
depends on the specifics of a particular implementation, not on the 
abstract properties of the algorithm used.

Possibly the worst part is that, unless you program in some horribly 
low-level language, you have no control over any of this.

Post a reply to this message

> As the paper says, a stupid O(n^2) algorithm could be *faster* than a 
> sophisticated algorithm with O(log n) or even O(1) time-complexity, all 
> due to cache effects that shouldn't be there in the first place. Decades 
> of research and development ruined.

What you are referring to are mathematical papers, they do not consider 
actual implementation on a machine, they are not meant to.  Computers have 
always had different amounts of memory with different speeds and access 
patterns, there are plenty of papers that take this into account.  You 
cannot just take a mathematical paper and expect it to work as described on 
a computer, you never have been able to.

> Now we have no way to predict performance, because it depends on cache 
> behaviour, which intimately depends on the specifics of a particular 
> implementation, not on the abstract properties of the algorithm used.

Sure, but it's always been like that and always will, there's nothing you 
can do about it.

> Possibly the worst part is that, unless you program in some horribly 
> low-level language, you have no control over any of this.

If your language/compiler is clever enough to switch around the order and 
storage of your code, then it should be clever enough to optimise for the 
memory structure of the machine.

Post a reply to this message

>> As the paper says, a stupid O(n^2) algorithm could be *faster* than a 
>> sophisticated algorithm with O(log n) or even O(1) time-complexity, 
>> all due to cache effects that shouldn't be there in the first place. 
>> Decades of research and development ruined.
> 
> You cannot just take a mathematical paper and expect it to 
> work as described on a computer, you never have been able to.

Back in the days of the 8-bit home computer, memory access really was a 
constant-time operation that always took 1 clock cycle. Unfortunately it 
seems that the larger a memory bank is, the slower it is to access. What 
this means is that a 2.2 GHz CPU only runs at 2.2 GHz if you use a tiny 
amount of data. If you try to random-access a large chunk of data, 
suddenly the program slows down to the speed of the RAM bus.

I guess the only consolation is that my CPU's L3 cache is probably 
bigger than the entire address space of the 6502...

> Sure, but it's always been like that and always will, there's nothing 
> you can do about it.

It wasn't always like that - but, as you say, there's nothing you can do 
about it.

>> Possibly the worst part is that, unless you program in some horribly 
>> low-level language, you have no control over any of this.
> 
> If your language/compiler is clever enough to switch around the order 
> and storage of your code, then it should be clever enough to optimise 
> for the memory structure of the machine.

Sure. But if it isn't, you can't do anything about it. You can't rewrite 
the compiler, after all...

Post a reply to this message

Am 14.06.2010 16:41, schrieb Invisible:

>> You cannot just take a mathematical paper and expect it to work as
>> described on a computer, you never have been able to.
>
> Back in the days of the 8-bit home computer, memory access really was a
> constant-time operation that always took 1 clock cycle. Unfortunately it
> seems that the larger a memory bank is, the slower it is to access. What
> this means is that a 2.2 GHz CPU only runs at 2.2 GHz if you use a tiny
> amount of data. If you try to random-access a large chunk of data,
> suddenly the program slows down to the speed of the RAM bus.

(1) Home computers were toys.

(2) Capacity of memory basically has nothing to do with access speed. 
The effect you describe for that 2.2 GHz CPU is the effects due to L1 
and L2 caches - which aren't faster because they are smaller, but 
because (a) they're closer to the CPU core and (b) they're using faster 
(but more space-consuming) technology.

Post a reply to this message

clipka wrote:

> (1) Home computers were toys.

I saw at least one employee using a company-purchased C64 to run 
accounting software to do actual, productive work.

They might be considered toys *now*...

> (2) Capacity of memory basically has nothing to do with access speed. 

Really? So having more bits to decode requiring more address decode 
logic doesn't affect speed in any way? And neither does a larger die 
area necessasitating longer traces?

> The effect you describe for that 2.2 GHz CPU is the effects due to L1 
> and L2 caches - which aren't faster because they are smaller, but 
> because (a) they're closer to the CPU core and (b) they're using faster 
> (but more space-consuming) technology.

I gather that part of the problem is that having traces on the 
motherboard operating into the GHz frequency range isn't very feasible. 
(For reasons such as trace length and electronic interference.) But that 
would still mean that theoretically you could make a single chip that 
contains a couple of CPU cores plus (say) 2GB of RAM. The fact that 
nobody has ever done this indicates that it isn't possible for whatever 
reason.

Post a reply to this message

>> You cannot just take a mathematical paper and expect it to work as 
>> described on a computer, you never have been able to.
>
> Back in the days of the 8-bit home computer, memory access really was a 
> constant-time operation that always took 1 clock cycle.

Sure, but just as an example, what's the fastest way to sort a 10 KB array 
when you have 16 KB or RAM?  The mathematically efficient way won't 
necessarily be the quickest if you need to read/write to tape/disc rather 
than just using RAM.  Also some operations were free (eg shifting when 
adding, other obscure things like that), a general mathematical paper won't 
take that into account when telling you the "best" algorithm for a task.

>> Sure, but it's always been like that and always will, there's nothing you 
>> can do about it.
>
> It wasn't always like that -

So your early 8bit computer could write to the tape at the same speed as 
RAM? :-O

>> If your language/compiler is clever enough to switch around the order and 
>> storage of your code, then it should be clever enough to optimise for the 
>> memory structure of the machine.
>
> Sure. But if it isn't, you can't do anything about it. You can't rewrite 
> the compiler, after all...

If your compiler changes the order that data is stored, or the order you 
access it, but doesn't take into account how this affects performance, then 
IMO it's broken.  Use a different compiler that either leaves the order 
alone (so you can optimise it yourself) or optmises it for you.

Post a reply to this message

>>> You cannot just take a mathematical paper and expect it to work as 
>>> described on a computer, you never have been able to.
>>
>> Back in the days of the 8-bit home computer, memory access really was 
>> a constant-time operation that always took 1 clock cycle.
> 
> Sure, but just as an example, what's the fastest way to sort a 10 KB 
> array when you have 16 KB or RAM?  The mathematically efficient way 
> won't necessarily be the quickest if you need to read/write to tape/disc 
> rather than just using RAM.

Then you use a specialised external-sort. More to the point, you *know* 
that you're going to need an external-sort. Your program doesn't just 
magically run 500x slower than you'd expected.

> Also some operations were free (eg shifting 
> when adding, other obscure things like that), a general mathematical 
> paper won't take that into account when telling you the "best" algorithm 
> for a task.

Sure. But if one algorithm takes 5,000 operations (some of which might 
be free) and another takes 72,000,000,000 operations, which one is 
fastest? On the computers of old, the answer was self-evident. Today, it 
might well be that the latter is actually faster.

>>> Sure, but it's always been like that and always will, there's nothing 
>>> you can do about it.
>>
>> It wasn't always like that -
> 
> So your early 8bit computer could write to the tape at the same speed as 
> RAM? :-O

More like in the early days, if it didn't fit in RAM, you just couldn't 
do it at all. Today if it doesn't fit in RAM, the OS makes the computer 
pretend it has more RAM than it does (with the *minor issue* of a vast 
slowdown and halving the life of your harddrive).

>>> If your language/compiler is clever enough to switch around the order 
>>> and storage of your code, then it should be clever enough to optimise 
>>> for the memory structure of the machine.
>>
>> Sure. But if it isn't, you can't do anything about it. You can't 
>> rewrite the compiler, after all...
> 
> If your compiler changes the order that data is stored, or the order you 
> access it, but doesn't take into account how this affects performance, 
> then IMO it's broken.  Use a different compiler that either leaves the 
> order alone (so you can optimise it yourself) or optmises it for you.

How about if the order just plain isn't defined in the first place? Or 
if the runtime system is storing auxhilery data which you don't know about?

Post a reply to this message

Invisible wrote:
> but RAM is still roughly the same speed.

No it's not. RAM used to take several microseconds. Drum memory was on the 
order of miliseconds.

> the time complexity of your algorithm is now *irrelevant*. The *only* 
> thing that matters now is cache behaviour.

Only irrelevant if all the data you need fits in cache. If you have a 300Gb 
data set like the paper says, your L1 cache isn't going to be nearly as 
important.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

clipka wrote:
> (2) Capacity of memory basically has nothing to do with access speed. 

Of course it does. You have speed-of-light delay and address line cascading 
to decode. The slowness isn't due primarily to accessing the memory cells. 
It's due to the cascade of gates you have to go thru to decode the address 
to figure out which cell. That's why video memory can be so much faster than 
CPU memory - there's an access pattern (the video beam scan) that can be 
used to speed up address decoding.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Invisible wrote:
> contains a couple of CPU cores plus (say) 2GB of RAM. 

What makes you think nobody has done this?

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Invisible wrote:
> More like in the early days, if it didn't fit in RAM, you just couldn't 
> do it at all. 

Not even close to true. People took it into account. You don't think 
WordStar could handle a document >64K?  Indeed, the whole point of an 
external sort was to handle what didn't fit in RAM.

Nowadays, people throw processing at it and let the OS handle paging.

And of course, you still get people dealing with the heirarchy explictly, 
like google, who even deals with the heirarchy of "on a disk on the same 
machine, on a disk on a different machine in the same rack, on a disk on a 
machine in a different rack in the same building, on a disk on a machine in 
a different building in the same state, etc."

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Am 14.06.2010 17:12, schrieb Invisible:
> clipka wrote:
>
>> (1) Home computers were toys.
>
> I saw at least one employee using a company-purchased C64 to run
> accounting software to do actual, productive work.
>
> They might be considered toys *now*...
>
>> (2) Capacity of memory basically has nothing to do with access speed.
>
> Really? So having more bits to decode requiring more address decode
> logic doesn't affect speed in any way?

I don't think so. Essentially, all you need to decode an address is a 
huge AND gate with some inputs inverted (and no, multi-input gates are 
/not/ normally designed as a tree of 2-input gates - they're simply 
extend on the 2-input gate design by adding just a few inputs and 
transistors more). Of course you need more of those gates, and therefore 
stronger drivers for the address lines to deal with the parasitic 
capacitance of the gates' inputs.

 > And neither does a larger die
> area necessasitating longer traces?

That, yes. But that's negligible compared with the distance between CPU 
and memory slot.

AFAIK, the most time-consuming thing about DRAM is the time it takes to 
charge, discharge or read out the capacitors comprising the memory cells.

> I gather that part of the problem is that having traces on the
> motherboard operating into the GHz frequency range isn't very feasible.
> (For reasons such as trace length and electronic interference.) But that
> would still mean that theoretically you could make a single chip that
> contains a couple of CPU cores plus (say) 2GB of RAM. The fact that
> nobody has ever done this indicates that it isn't possible for whatever
> reason.

I guess it's impractical, because...

(1) RAM requirements are pretty different, so you'd need a lot more CPU 
models (which would skyrocket the development, maintenance and 
production set-up costs per CPU) - and you couldn't just buy a few extra GB.

(2) You wouldn't win much speed because DRAM technology is inherently 
slow, and SRAM technology (as used in caches) is prohibitively large

(3) I might be wrong, but I guess producing DRAM memory in a 40nm 
process would be ineffective: You do want certain minimum dimensions for 
the capacitors and insulation anyway, in order to reduce self-discharge 
effects.

(4) Integrating 2GB into the CPU would require a lot of additional die 
space even with DRAM, increasing the per-die production cost - not only 
because you get less CPUs out of a wafer, but also because increasing 
the die space gives you an increased per-die probability of a failure, 
reducing production yield.

Post a reply to this message

clipka wrote:
> I don't think so. Essentially, all you need to decode an address is a 
> huge AND gate with some inputs inverted 

In theory true. In practice, there's a certain amount of fan-in you can 
handle in any one gate.  The limit is about 8 inputs, afaik. My knowledge on 
this particular bit is probably several fab generations out of date.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Am 14.06.2010 18:58, schrieb Darren New:
> clipka wrote:
>> I don't think so. Essentially, all you need to decode an address is a
>> huge AND gate with some inputs inverted
>
> In theory true. In practice, there's a certain amount of fan-in you can
> handle in any one gate. The limit is about 8 inputs, afaik. My knowledge
> on this particular bit is probably several fab generations out of date.

Even then, you'd have some log8(N) dependency of gate levels needed, 
where N isn't even the amount of memory, but the number of address lines.

1 level:   8 address lines - up to 256 words (*)
2 levels: 64 address lines - up to 16 Exawords

(* where the word size solely depends on your data bus width)

If main memory sizes should increase with the same speed as today, that 
should give us another 20 to 30 years until a computer for private or 
office use will need 3 levels of address decoding gates in its RAM modules.

Post a reply to this message

Am 14.06.2010 17:58, schrieb Darren New:
> clipka wrote:
>> (2) Capacity of memory basically has nothing to do with access speed.
>
> Of course it does. You have speed-of-light delay and address line
> cascading to decode. The slowness isn't due primarily to accessing the
> memory cells. It's due to the cascade of gates you have to go thru to
> decode the address to figure out which cell. That's why video memory can
> be so much faster than CPU memory - there's an access pattern (the video
> beam scan) that can be used to speed up address decoding.

If gates are so slow, how come SRAM is so much faster? After all, even 
the memory cells themselves consist of gates there.

I guess the advantage of the access pattern in video memory is a 
different one: It allows easy /prediction/ of the next address to fetch, 
so readout of DRAM cells can be initiated well before the data is 
actually needed, so it's available just in time - farewell latency.

Post a reply to this message

Am 14.06.2010 17:45, schrieb Invisible:

>> Sure, but just as an example, what's the fastest way to sort a 10 KB
>> array when you have 16 KB or RAM? The mathematically efficient way
>> won't necessarily be the quickest if you need to read/write to
>> tape/disc rather than just using RAM.
>
> Then you use a specialised external-sort. More to the point, you *know*
> that you're going to need an external-sort. Your program doesn't just
> magically run 500x slower than you'd expected.

Which is just the point to learn from this: You should (ideally) know 
that the very same is true for today's computers, so that you know where 
such "magical" slowdowns come from, and what can be done against it.

> More like in the early days, if it didn't fit in RAM, you just couldn't
> do it at all.

Nonsense. Datacenters have been using slow memory, such as magnetic 
tapes, for ages. "If it all fits in RAM, then congratulations!" would 
have been closer to the mark back then I guess.

 > Today if it doesn't fit in RAM, the OS makes the computer
> pretend it has more RAM than it does (with the *minor issue* of a vast
> slowdown and halving the life of your harddrive).

I'd rather put it this way: Today, if it doesn't fit in RAM, the OS 
helps you "juggling" the memory chunks to work on. (And if it doesn't 
fit in L1 or L2 cache, the CPU provides essentially the same service.) 
Which makes life much easier in a world where you don't know how much 
RAM you'll have when programming the software. (Back then, you /did/ 
know the specs of the one machine you wrote your programs for.) Plus, it 
allows much easier and faster (and therefore more economical) design of 
software where runtime performance doesn't matter that much.

(As for harddrive life, I guess that depends on your harddrive.)

Post a reply to this message

clipka wrote:
> Even then, you'd have some log8(N) dependency of gate levels needed, 
> where N isn't even the amount of memory, but the number of address lines.

I'm not really following...

> 1 level:   8 address lines - up to 256 words (*)
> 2 levels: 64 address lines - up to 16 Exawords

Except ... you need that fan-in for each word you address. Now you have a 
problem of fan-out, as well, if I'm visualizing what you're saying correctly.

In theory, any logic function (including an entire CPU) can be built from 
two levels of gates. In practice, the fan-in and fan-out kills you, because 
you can't have 256 fan-outs going into each of 256 additional gates.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

clipka wrote:
> If gates are so slow, how come SRAM is so much faster? After all, even 
> the memory cells themselves consist of gates there.

Well, DRAM adds its own slowness, yes. But even with SRAM, having 16 gig of 
SRAM is going to be slower than having 1 Meg of SRAM.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

>> Today if it doesn't fit in RAM, the OS makes the computer
>> pretend it has more RAM than it does (with the *minor issue* of a vast
>> slowdown and halving the life of your harddrive).
> 
> I'd rather put it this way: Today, if it doesn't fit in RAM, the OS 
> helps you "juggling" the memory chunks to work on. (And if it doesn't 
> fit in L1 or L2 cache, the CPU provides essentially the same service.) 
> Which makes life much easier in a world where you don't know how much 
> RAM you'll have when programming the software. (Back then, you /did/ 
> know the specs of the one machine you wrote your programs for.) Plus, it 
> allows much easier and faster (and therefore more economical) design of 
> software where runtime performance doesn't matter that much.

Well, there is that, yes. But I (and presumably everybody else) would 
prefer it if we could actually make RAM really, really fast...

> (As for harddrive life, I guess that depends on your harddrive.)

If stuff is being swapped out just because it isn't being used right 
now, that's fine. But watch a program trying to random-access several GB 
of data when you don't have multiple GB of RAM. It's an extremely 
efficient way to give your HD a *very* strenuous workout! ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Am 14.06.2010 20:34, schrieb Orchid XP v8:
>>> Today if it doesn't fit in RAM, the OS makes the computer
>>> pretend it has more RAM than it does (with the *minor issue* of a vast
>>> slowdown and halving the life of your harddrive).
>>
>> I'd rather put it this way: Today, if it doesn't fit in RAM, the OS
>> helps you "juggling" the memory chunks to work on. (And if it doesn't
>> fit in L1 or L2 cache, the CPU provides essentially the same service.)
>> Which makes life much easier in a world where you don't know how much
>> RAM you'll have when programming the software. (Back then, you /did/
>> know the specs of the one machine you wrote your programs for.) Plus,
>> it allows much easier and faster (and therefore more economical)
>> design of software where runtime performance doesn't matter that much.
>
> Well, there is that, yes. But I (and presumably everybody else) would
> prefer it if we could actually make RAM really, really fast...

... which will never ever again happen for main memory, at least not in 
the sense of being equally fast as whatever caches we'll be using then: 
We'll always have to live with memory being arranged in multiple tiers 
of different speed.


>> (As for harddrive life, I guess that depends on your harddrive.)
>
> If stuff is being swapped out just because it isn't being used right
> now, that's fine. But watch a program trying to random-access several GB
> of data when you don't have multiple GB of RAM. It's an extremely
> efficient way to give your HD a *very* strenuous workout! ;-)

Sure, but some HDs are designed for this type of life.

BTW, it's not harddrive life that worries me in such situations, but the 
bare struggle to get the system's attention back. Try killing a 
swapping-mad program when it keeps thrashing the task manager out of 
main memory... >_<

Post a reply to this message

clipka wrote:

> BTW, it's not harddrive life that worries me in such situations, but the 
> bare struggle to get the system's attention back. Try killing a 
> swapping-mad program when it keeps thrashing the task manager out of 
> main memory... >_<

Heh. Fun... Actually, the one I usually have trouble with is Alt+Tab 
from a game back to the Windows desktop. Takes several lifetimes in both 
directions. No idea why.

One thing I discovered back at uni: If your Java program accidentally 
goes into an infinite loop, it dies almost instantly with a stack 
overflow. If your Smalltalk program accidentally loops forever, it's 
usually a few minutes before you realise that it's actually filling the 
entire VM address space with garbage. Now try stopping it. :-)

Literally, it's so determined to follow your instructions as efficiently 
as possible that for a while you don't even realise what's wrong. It 
just looks like it's "busy".

Of course, infinite loops are much, much more common in Smalltalk. A 
very common idiom is to write

#new
   super new.
   ...stuff...

But if, by some slip, you instead write

#new
   self new.
   ...stuff...

...then calling #new immediately calls #new, creating an endless 
allocation loop. o_O

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> One thing I discovered back at uni: If your Java program accidentally
> goes into an infinite loop, it dies almost instantly with a stack
> overflow.

That's just because the VM only claims a small amount of RAM to start with...
quite irritating actually, it took me ages to work out I had to increase its
allocation to get my fractal plotter to be able to hold a decent image :-)

(but then it was too slow anyway so I rewrote it in C)

Post a reply to this message

clipka wrote:
> BTW, it's not harddrive life that worries me in such situations, but the 
> bare struggle to get the system's attention back. Try killing a 
> swapping-mad program when it keeps thrashing the task manager out of 
> main memory... >_<

Hell, even if it's just copying big files, you have the same problem.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Darren New wrote:
> Invisible wrote:
>> contains a couple of CPU cores plus (say) 2GB of RAM. 
> 
> What makes you think nobody has done this?

Au contrare, what makes you think that somebody *has* done this?

Post a reply to this message

>> One thing I discovered back at uni: If your Java program accidentally
>> goes into an infinite loop, it dies almost instantly with a stack
>> overflow.
> 
> That's just because the VM only claims a small amount of RAM to start with...
> quite irritating actually, it took me ages to work out I had to increase its
> allocation to get my fractal plotter to be able to hold a decent image :-)
> 
> (but then it was too slow anyway so I rewrote it in C)

Smalltalk seemed to be very, very good at handling large amounts of 
objects in RAM. It didn't complain or anything, it just got on with it.

Unfortunately, usually the only reason for this happening was programmer 
error. :-/

Haskell (or rather, GHC) is similar. It will happily eat several GB of 
VM very quickly. The difficulty isn't figuring out how to allocate 
enough space; it's finding the magic CLI switch that tells it to quit 
rather than eat all available RAM!

(There's a switch that makes it die if the program tries to allocate 
more than X. If you happen to know that your program can only possibly 
require a few MB, set this switch and if there's a bug, the program will 
die rather than kill you.)

Post a reply to this message

In other news... I get the impression that the world is probably heading 
towards NUMA anyway. Not sure precisely how that changes the picture - 
other than making it much, much more complicated...

(I'm not sure, but I think it might mean that you have explicit control 
over what is stored where and when it gets moved, which could be a win 
if compilers are smart enough to do the right thing.)

Post a reply to this message

scott wrote:
> Sure, but just as an example, what's the fastest way to sort a 10 KB array
> when you have 16 KB or RAM?

You just go and do it. I'm sure the sorting algorithm fits in the remaining 
6KB.

Or did you get those two numbers backwards?

Post a reply to this message

Invisible wrote:
> Darren New wrote:
>> Invisible wrote:
>>> contains a couple of CPU cores plus (say) 2GB of RAM. 
>>
>> What makes you think nobody has done this?
> 
> Au contrare, what makes you think that somebody *has* done this?

Well, two gig is a bit high, but several hundred meg is not uncommon.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

>>> What makes you think nobody has done this?
>>
>> Au contrare, what makes you think that somebody *has* done this?
> 
> Well, two gig is a bit high, but several hundred meg is not uncommon.

Like I said, it seems there's a relationship between capacity and speed, 
such that by the time you get to this size, there wouldn't be much speed 
advantage to putting it on-chip.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> Like I said, it seems there's a relationship between capacity and speed, 
> such that by the time you get to this size, there wouldn't be much speed 
> advantage to putting it on-chip.

In all the cases I know about, the problem was not that, but that there was 
a concern that there was a cap on the amount of memory.

Either you need X meg of memory to do what your chip is designed to do, or 
you want an arbitrary "lots" of memory. (E.g., you're either building a 
phone that doesn't run apps not installed when you built it, or you want to 
run as many apps at once as you want.)  If you ever want to add RAM, you 
need to have the interface stuff for it anyway.  If you don't ever want to 
add RAM, chances are you don't need more than a few hundred meg to support 
your single-chip application.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

On 6/14/2010 2:29 PM, Orchid XP v8 wrote:
> clipka wrote:
>
>> BTW, it's not harddrive life that worries me in such situations, but
>> the bare struggle to get the system's attention back. Try killing a
>> swapping-mad program when it keeps thrashing the task manager out of
>> main memory... >_<
>
> Heh. Fun... Actually, the one I usually have trouble with is Alt+Tab
> from a game back to the Windows desktop. Takes several lifetimes in both
> directions. No idea why.
>
> One thing I discovered back at uni: If your Java program accidentally
> goes into an infinite loop, it dies almost instantly with a stack
> overflow. If your Smalltalk program accidentally loops forever, it's
> usually a few minutes before you realise that it's actually filling the
> entire VM address space with garbage. Now try stopping it. :-)
>

You can do it in C#, too .. I forget exactly what I was writing, but I 
threw something into an infinite loop that allocated objects and added 
them to a list. A split second after I hit F5 to run the program, I 
realized my mistake. That was enough time for it to allocate some 4GB of 
memory, By the time I reacted to stop the program it had ballooned up to 
10GB.

64 bit is great, but try dealing with that sort of memory stress (My 
system has 4GB of memory ...)




-- 
~Mike

Post a reply to this message

Mike Raiford wrote:

> 64 bit is great, but try dealing with that sort of memory stress (My 
> system has 4GB of memory ...)

Generally that kind of thing isn't so bad though. All the garbage that 
gets paged out never gets paged back in again. Assuming you can page in 
the code to stop the damned thing, once it's been killed the system 
takes a little while to page all the live stuff back in, and then it 
goes back to normal.

Now, when your program is actively *using* several GB of RAM... that's 
not so fun. (!!)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 6/15/2010 2:09 PM, Orchid XP v8 wrote:
>
> Now, when your program is actively *using* several GB of RAM... that's
> not so fun. (!!)
>

Photoshop did this ... I was building an image out of a stack of shots 
with several shots at full resolution 16-bit per channel color. The 
algorithm that determines which parts were in sharpest focus apparently 
set out to spread itself out as much as possible in memory.

I walked away for a few minutes after starting the process, came back 
and tried to switch to my browser, and found the system unresponsive. It 
stayed that way for about 30 min before task manager finally appeared. 
Again, 10GB of memory, but actively working with that 10GB. I had other 
stuff I hadn't saved yet, and wanted a chance to save, so I waited .... 
before I killed PS.

-- 
~Mike

Post a reply to this message

>> Now, when your program is actively *using* several GB of RAM... that's
>> not so fun. (!!)
> 
> Photoshop did this ... I was building an image out of a stack of shots 
> with several shots at full resolution 16-bit per channel color. The 
> algorithm that determines which parts were in sharpest focus apparently 
> set out to spread itself out as much as possible in memory.
> 
> I walked away for a few minutes after starting the process, came back 
> and tried to switch to my browser, and found the system unresponsive. It 
> stayed that way for about 30 min before task manager finally appeared. 
> Again, 10GB of memory, but actively working with that 10GB. I had other 
> stuff I hadn't saved yet, and wanted a chance to save, so I waited .... 
> before I killed PS.

Pff. Accidentally write some Haskell code with the wrong strictness 
properties and watch it swallow several *hundred* GB by mistake... It's 
not even funny.

Usually very easy to kill though, if that's any consolation. (The key, 
as I said, is to set the maximum heap size to something smaller than 
physical RAM - especially if you know your program isn't supposed to 
need lots of RAM anyway...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> Generally that kind of thing isn't so bad though. All the garbage that 
> gets paged out never gets paged back in again. 

Sometimes when you kill a big process, it actually does have to read 
everything back in, to run finalizers or whatever, and to generally 
deallocate memory.  It's not unusual to hit ctrl-C on a CLI-driven program 
and have it take a minute or more to exit even if you're not catching signals.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Darren New wrote:
> Orchid XP v8 wrote:
>> Generally that kind of thing isn't so bad though. All the garbage that 
>> gets paged out never gets paged back in again. 
> 
> Sometimes when you kill a big process, it actually does have to read 
> everything back in, to run finalizers or whatever, and to generally 
> deallocate memory.  It's not unusual to hit ctrl-C on a CLI-driven 
> program and have it take a minute or more to exit even if you're not 
> catching signals.

I haven't seen that problem with programs I've written myself (which 
obviously don't use finalisers), but I've seen other software do this...

Post a reply to this message

>> Sure, but just as an example, what's the fastest way to sort a 10 KB 
>> array
>> when you have 16 KB or RAM?
>
> You just go and do it. I'm sure the sorting algorithm fits in the 
> remaining
> 6KB.
>
> Or did you get those two numbers backwards?

Actually I was thinking about algorithms that are not in-place (eg radix 
sort).  Whilst in a mathematical sense they might seem to be faster, if you 
start having to use slower storage (where some other algorithm doesn't) then 
obviously this might no longer be the case.

Post a reply to this message

>> One thing I discovered back at uni: If your Java program accidentally
>> goes into an infinite loop, it dies almost instantly with a stack
>> overflow.
> 
> That's just because the VM only claims a small amount of RAM to start with...
> quite irritating actually, it took me ages to work out I had to increase its
> allocation to get my fractal plotter to be able to hold a decent image :-)
> 
> (but then it was too slow anyway so I rewrote it in C)

Actually, I think this is probably bogus.

Any object data goes in the heap, not the stack. A *stack* overflow 
indicates a sequence of method calls nested too deeply.

Heck, Haskell programs (more exactly, GHC-compiled Haskell programs) 
often die from a *stack* overflow very quickly. But they don't die from 
*heap* exhaustion (unless you set the magic flag).

Post a reply to this message