Re: MALLOC

From: Joseph M. Newcomer (newcomer_at_flounder.com)
Date: 05/31/04 

Date: Mon, 31 May 2004 00:05:36 -0400

For oversized graphics, it is probably reasonable, but in that case, "paging" needs to
worry about third-order effects. My observation about orders-of-magnitude improvements in
such algorithms are based on the observation that naive algorithms usually have poor
paging behavior, and worse L2/L1 cache behavior. For example, to convolve a gigabyte
image, you are best off doing a large segment (e.g., 64K, 1MB, something else like that)
through some large number of iterations, then move to the next segment, and each segment
is scanned in a way that optimizes cache behavior. This is better than doing
row-major-order across the whole image, or column-major-order, or whatever.

The classic example is the SpecMark for matrix inversion. On the RISC-6000 using the
normal FORTRAN compiler, it benched out at 45 SPECmarks (larger number is better). IBM
wrote a program, in FORTRAN, that took some specifications of the cache line behavior
(which was different on different models), then read the original SPECmark program. It
then emitted a second FORTRAN program which performed the same algorithm, but optimized
for cache hits, and they got 900 SPECmarks. That's a 20:1 performance improvement! It was
for something like 10Kx10K elements, if I recall correctly. Now all the SPECmark
benchmarkers use a similar technique. But it shows what you can accomplish on regular
data.

On Sun, 30 May 2004 19:39:55 -0700, "Alexander Grigoriev" <alegr@earthlink.net> wrote:

>For audio application, such a large allocation and custom paging is kind of
>overkill. But it may have its use for oversized graphics.
>
>"Joseph M. Newcomer" <newcomer@flounder.com> wrote in message
>news:k8rkb01flnbcsbl53uudad6123traa04b0@4ax.com...
>> Paging isn' treally a good model, for the reason you point out. There can
>be no
>> :"lookahead" in paging, whereas if you use ordinary file I/O there CAN be
>lookahead. I
>> think you are trying to solve the wrong problem with an overly complex
>mechanism, and
>> trying to write a paging mechanism seems unnecessary given that ordinary
>sequential file
>> I/O would suffice (we use multimedia I/O calls, which work on structured
>files, and can
>> keep up indefinitely with CD-quality audio)
>> joe
>>
>> On Sun, 30 May 2004 10:47:12 -0700, "Alexander Grigoriev"
><alegr@earthlink.net> wrote:
>>
>> >Another possible implementation is to use your own paging mechanism, with
>> >larger granularity and guaranteed contiguosity (?) of the paging file. It
>> >takes a VirtualAlloc of uncommitted memory and you should handle all
>> >exceptions on access to uncommitted memory.
>> >
>> >Windows paging is kind of crappy, it seems to use 4KB pagefile
>granularity
>> >and doesn't seem to do read-ahead for that reason. The better approach
>would
>> >be to allocate pagefile space in 64 KB chunks, and page in all
>non-present
>> >pages in a 64 KB chunk, when a page fault occurs inside it. I also cannot
>> >understand why (with the modern RAM sizes) it doesn't read a whole
>EXE/DLL
>> >into memory on LoadLibrary or process startup, it would speed up the
>startup
>> >greatly.
>> >
>> >Of course, the OP problem doesn't need such large allocation, anyway.
>> >
>> >"Joseph M. Newcomer" <newcomer@flounder.com> wrote in message
>> >news:uehib0pvhdbq54v4esv9sj1u2oa4ja10aj@4ax.com...
>> >> First, dream on. The chances that you will be able to allocate 1GB of
>> >memory is
>> >> vanishingly small, even if you call VirtualAlloc.
>> >>
>> >> Physical RAM size has nothing to do with the ability to allocate the
>> >memory. You need a
>> >> swapfile of a minimum of 1GB, and I would suggest 1.5GB to 2GB But you
>> >need a whopping lot
>> >> of main memory to get respectable performance.because if memory is low,
>> >you spend all your
>> >> time swapping pages in and out.
>> >>
>> >> Why do you need 1GB? There are often better alternatives to such
>massive
>> >allocations. For
>> >> example memory-mapped files where you map a view to pieces of the file.
>> >>
>> >> But while you see 2GB of virtual address space, a lot of that is
>already
>> >committed to
>> >> various DLLs, your heap, etc., and finding 1GB of contiguous heap is
>very
>> >low probability.
>> >> On end-user machines, you can assume the probability is zero.
>> >>
>> >> You are more likely to be able to allocate two 0.5GB chunks, or 10
>100MB
>> >chunks.
>> >>
>> >> If you're seriious about needing this much memory, buy an AMD64 box,
>which
>> >has an 8TB user
>> >> address space.
>> >> joe
>> >>
>> >> On Sat, 29 May 2004 07:41:03 -0700, "VIJAY"
>> ><anonymous@discussions.microsoft.com> wrote:
>> >>
>> >> >I need to allocate 1 gb of data in memory.( ram).. how do i do this??
>> >> >but if the physical ram size is small and how the data is loaded..
>> >> >any suggestion will be appreciated..
>> >> > VIJAY
>> >>
>> >> Joseph M. Newcomer [MVP]
>> >> email: newcomer@flounder.com
>> >> Web: http://www.flounder.com
>> >> MVP Tips: http://www.flounder.com/mvp_tips.htm
>> >
>>
>> Joseph M. Newcomer [MVP]
>> email: newcomer@flounder.com
>> Web: http://www.flounder.com
>> MVP Tips: http://www.flounder.com/mvp_tips.htm
>

Joseph M. Newcomer [MVP]
email: newcomer@flounder.com
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm

Relevant Pages