headers
Mark Engelberg | 3 Jan 2011 00:40
Picon

Pearls of Functional Algorithm Design question

I'm currently reading the excellent Haskell-based book "Pearls of
Functional Algorithm Design".  I have a question about Chapter 2, the
"surpassing problem".

According to the book, "since join takes linear time, table is
computer in O(n log n) steps".

However, as far as I can tell, join takes linear time proportional to
the number of elements in *table*, and the number of elements in table
is potentially as large as n^2 where n is the length of the original
list.  So it seems like a quadratic algorithm or worse, to me.  What
am I missing?

Thanks,

Mark
Permalink | Reply | 1 comment |
headers
Mark Engelberg | 3 Jan 2011 11:49
Picon

Re: Pearls of Functional Algorithm Design question

Richard sent me a note offlist which quickly cleared up my
misconception.  I was mistaken that table could contain n^2 elements.
A closer reading of the definition of table makes it clear that it
will have n elements, so the n log n bound makes perfect sense to me
now.

Thanks!

--Mark

P.S.  I highly recommend the book.
Permalink | Reply | 0 comments |
headers
Ben Millwood | 4 Jan 2011 04:49
Picon
Favicon
Gravatar

ANNOUNCE: haskell-src-meta 0.3

Hello,

I'm pleased to announce the recent release of haskell-src-meta 0.3.

haskell-src-meta is a package originally written by Matt Morrow to
provide a translation from the syntax tree provided by
haskell-src-exts to template haskell syntax. Essentially this allows
TH code to be parsed from a string, and is used in several quasiquoter
libraries.

The biggest reason for 0.3 is support for GHC 7 and TH 2.5. In
addition to that, there is also better support for inline pragmas, and
a smaller API. The original haskell-src-meta had a lot of neat ideas
all in one place, and while they were quite useful, they were also
irritating to maintain and made the version number unstable (keeping
in line with the PVP). In an attempt to address this, I've moved the
two most useful quasiquoters to their own new package -
applicative-quoters - and moved the rest to an unexported 'examples'
directory. I intend to do more to reduce the exposed API, but I
thought I would make this release as soon as possible so that my
reverse dependencies could start building again.

I welcome contributions and contributors. This package is not in any
real sense "mine" so I am happy to grant committer access to the
github or joint maintainership to anyone with an interest in doing so.
If you find bugs, there is an issue tracker, or if you want to discuss
issues, there is a wiki:

https://github.com/benmachine/haskell-src-meta
(Continue reading)

Permalink | Reply | 1 comment |
headers
Simon Peyton-Jones | 4 Jan 2011 14:05
Picon
Favicon
Gravatar

CFP: Workshop on Intermediate Representations: deadline Jan 21

Friends

 

Happy new year!  I’m on the PC for Workshop on Intermediate Representations; do consider submitting a paper. 

 

Simon

 

WIR 2011: Workshop on Intermediate Representations 2011

http://researchr.org/conference/wir-2011

The intermediate representation is the core of any program transformation tool. Its design has a significant impact on the simplicity, efficiency, and effectiveness of program transformations. The developments in concurrent programming, integrated development environments, and domain-specific languages pose new requirements on intermediate representations. This workshop provides a forum to discuss current trends and experiences in the design, implementation, and application of intermediate representations.

Co-located with CGO 2011

Conference Dates

Submissions:

January 21, 2011

Notification:

February 25, 2011

Event:

April 2, 2011-April 2, 2011

 

_______________________________________________
Haskell mailing list
Haskell <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Permalink | Reply | 0 comments |
headers
Clemens Grelck | 4 Jan 2011 20:13
Picon
Picon
Favicon

Call for Papers: PAPP 2011 (deadline extended)

New deadline: January 15, 2011 !!

Eighth International Workshop on
Practical Aspects of High-Level Parallel Programming (PAPP 2011)

part of The International Conference on Computational Science
June 1-3, 2011, Tsukuba, Japan

http://www.papp-workshop.org

AIMS AND SCOPE

Computational Science applications are more and more complex to
develop and require more and more computing power. Sequential
computing cannot go further. Major companies in the computing industry
now recognise the urgency of re-orienting an entire industry towards
massively parallel computing.

Parallel and grid computing are solutions to the increasing need for
computing power. The trend is towards the increase of cores in
processors, the number of processors and the need for scalable
computing everywhere. But parallel and distributed programming is
still dominated by low-level techniques such as send/receive message
passing. Thus high-level approaches should play a key role in the
shift to scalable computing in every computer.

Algorithmic skeletons, parallel extensions of functional languages
such as Haskell and ML, parallel logic and constraint programming,
parallel execution of declarative programs such as SQL queries,
genericity and meta-programming in object-oriented languages,
etc. have produced methods and tools that improve the
price/performance ratio of parallel software, and broaden the range of
target applications. Also, high level languages offer a high degree of
abstraction which ease the development of complex systems. Moreover,
being based on formal semantics, it is possible to certify the
correctness of critical parts of the applications.

The PAPP workshop focuses on practical aspects of high-level parallel
programming: design, implementation and optimisation of high-level
programming languages, semantics of parallel languages, formal
verification, design or certification of libraries, middle-wares and
tools (performance predictors working on high-level parallel/grid
source code, visualisations of abstract behaviour, automatic hot-spot
detectors, high-level GRID resource managers, compilers, automatic
generators, etc.), application of proof assistants to parallel
applications, applications in all fields of computational science,
benchmarks and experiments. Research on high-level grid programming is
particularly relevant as well as domain specific parallel software.

The aim of all these languages and tools is to improve and ease the
development of applications (safety, expressivity, efficiency,
etc.). Thus the PAPP workshop focuses on applications.

The PAPP workshop is aimed both at researchers involved in the
development of high level approaches for parallel and grid computing
and computational science researchers who are potential users of these
languages and tools.  Topics

We welcome submission of original, unpublished papers in English on
topics including:

     * applications in all fields of high-performance computing
       and visualisation (using high-level tools)
     * high-level models (CGM, BSP, MPM, LogP, etc.) and tools for
       parallel and grid computing
     * high-level parallel language design, implementation and optimisation
     * practical aspects of computer assisted verification for
       high-level parallel languages
     * modular, object-oriented, functional, logic, constraint
       programming for parallel, distributed and grid computing systems
     * algorithmic skeletons, patterns and high-level parallel libraries
     * generative (e.g. template-based) programming with algorithmic skeletons,
       patterns and high-level parallel libraries
     * benchmarks and experiments using such languages and tools

PAPER SUBMISSION AND PUBLICATION

Prospective authors are invited to submit full papers in English
presenting original research. Submitted papers must be unpublished and
not submitted for publication elsewhere. Papers will go through a
rigorous reviewing process. Each paper will be reviewed by at least
three referees. The accepted papers will be published in the Procedia
Computer Science series, as part of the ICCS proceedings.

Submission must be done through the ICCS website.

We invite you to submit a full paper of at most 10 pages describing
new and original results, no later than January 8, 2011. Submission
implies the willingness of at least one of the authors to register and
present the paper.

Accepted papers should be presented at the workshop.

IMPORTANT DATES

     * January 15, 2011: Full paper due
     * February 20, 2011: Notification
     * March 7, 2011: Camera-ready paper due

PROGRAMME COMMITTEE

     * Marco Aldinucci (University of Torino, Italy)
     * Jost Berthold (University of Copenhagen, Denmark)
     * Kento Emoto (University of Tokyo, Japan)
     * Frédéric Gava (University Paris-East, France)
     * Alexandros Gerbessiotis (NJIT, USA)
     * Clemens Grelck (University of Amsterdam, Netherlands)
     * Hideya Iwasaki (The University of Electro-communications, Japan)
     * Roman Leshchinskiy (Standard Chartered Bank, UK)
     * Frédéric Loulergue, chair (University of Orléans, France)
     * Bruno Raffin (INRIA, France)
     * Aamir Shafi (NUST, Pakistan)
--

-- 
----------------------------------------------------------------------
Dr Clemens Grelck                                     Science Park 904
Universitair Docent                                  1098 XH Amsterdam
                                                              Nederland
Universiteit van Amsterdam
Instituut voor Informatica                       T +31 (0) 20 525 8683
                                                  F +31 (0) 20 525 7490
Office C3.105                               www.science.uva.nl/~grelck
----------------------------------------------------------------------
Permalink | Reply | 0 comments |
headers
Emanuel Kitzelmann | 5 Jan 2011 06:20
Picon

CfP: 4th Workshop on Approaches and Applications of Inductive Programming (AAIP 2011)

                    CALL FOR PAPERS

             4th International Workshop on
  Approaches and Applications of Inductive Programming
                       AAIP 2011

             July 19, 2011, Odense, Denmark

      http://www.cogsys.wiai.uni-bamberg.de/aaip11/

co-located with the
International ACM SIGPLAN Symposium on Principles and Practice of Declarative
Programming (PPDP 2011)
and the
International Symposium on Logic-Based Program Synthesis and Transformation
(LOPSTR 2011).

AIMS AND SCOPE

Inductive program synthesis or inductive programming (IP) is concerned with the
automated generation of general computer programs from incomplete
specifications such as input/output examples. IP particularly includes the
synthesis of programs that contain loops or recursive calls. This inductive
type of automated program synthesis is addressed by researchers in different
fields such as artificial intelligence, inductive logic programming,
evolutionary computation, symbolic computation, grammar inference, formal
methods, and functional programming. The aim of the AAIP workshop is to have a
common place to present and discuss research on all aspects of inductive
programming - including, but not limited to: Inductive programming algorithms,
techniques, and systems, heuristics, inductive biases, analysis of the
learnability of particular program classes, and the combination of
generate-and-test based and analytical techniques. We especially encourage
submissions on inductive programming challenge problems and real-world
applications of inductive programming in, e.g., computer-assisted software
engineering, end-user programming, and intelligent agents.

This is the fourth workshop on "Approaches and Applications of Inductive
Programming" and takes place for the first time in conjunction with PPDP and
LOPSTR.

We invite authors to submit papers reporting on original work in either of two
categories: full technical papers and short papers. Full papers should present
mature work. Short papers may be work in progress reports, descriptions of
system demonstrations, or position statements.

INVITED TALKS

TBA

PRESENTATION AND PUBLICATION INFORMATION

All accepted papers will be presented orally. Workshop (pre-)proceedings will
be published online and as a technical report. Furthermore, we plan to publish
selected and revised papers as a post-proceedings volume and sent a
corresponding request to Springer LNCS.

SUBMISSION GUIDELINES

Submitted papers must describe original work, be written in English and should
be formatted in the Springer Lecture Notes in Computer Science style:
http://www.springer.de/comp/lncs/authors.html

Submissions can either be full papers describing mature work or short papers
describing work in progress, a system demonstration, or make a position
statement. Full and short papers should not exceed 16 and 8 pages,
respectively, including bibliography and appendices. Papers should be submitted
as PDF via the AAIP 2011 submission webpage:
http://www.easychair.org/conferences/?conf=aaip2011

IMPORTANT DATES

April 3, 2011	Paper submission
May 16, 2011	Author notification
June 12, 2011	Camera-ready
July 19, 2011	Workshop

ORGANIZATION COMMITTEE

  * Emanuel Kitzelmann, International Computer Science Institute, Berkeley, USA
  * Ute Schmid, University of Bamberg, Germany

PROGRAM COMMITTEE

  * Ricardo Aler Mur, Universidad Carlos III de Madrid, Spain
  * Pierre Flener, Uppsala University, Sweden
  * Lutz Hamel, University of Rhode Island, Kingston, USA
  * Jose Hernandez-Orallo, Technical University of Valencia, Spain
  * Martin Hofmann, SAP Research & Development, Germany
  * Johan Jeuring, University of Utrecht, The Netherlands
  * Susumu Katayama, University of Miyazaki, Japan
  * Pieter Koopman, Radboud University Nijmegen, The Netherlands
  * Maria Jose Ramirez Quintana, Technical University of Valencia, Spain

CONTACT

aaip2011 <at> easychair.org

--

-- 
Dr. Emanuel Kitzelmann
International Computer Science Institute (ICSI)
1947 Center Street, Suite 600
Berkeley, CA 94704, USA

e-mail: emanuel AT icsi DOT berkeley DOT edu
phone: +1 510 666 2883
Permalink | Reply | 0 comments |
headers
Malcolm Wallace | 7 Jan 2011 19:39
Gravatar

Announce: ~Haskell 2011

The Haskell Language committee has had a quiet year.  Following the  
announcement of Haskell 2010 in Nov 2009 [1], and the publication of  
the 2010 Report in July 2010 [2], we found a distinct lack of complete  
new proposals to decide upon.  As a result, the committee has made the  
following decisions:

  (a) we wish to accept the NoDatatypeContexts proposal
      http://hackage.haskell.org/trac/haskell-prime/wiki/NoDatatypeContexts
  (b) this delta will be applied to the 2010 Report to form a new  
baseline;
  (c) we will _not_ issue a new language standard called 2011;
  (d) we intend to issue a new language standard in 2012;
  (e) the committee will continue for another year without new  
nominations.

However, let me make it clear that the apparent lull in committee  
activity does not mean there are no active proposals being made.  On  
the contrary, proposals for language features (and removals) are made  
by the community at large (that's you) - the committee's main role is  
not to make proposals, but to decide which to accept.  And there have  
in fact been a large number of proposals, but very few have made it  
all the way to the stage of producing a "language report delta" that  
could be accepted (or modified) by the committee.

So, I wish to declare "open season" on proposals for the 2012  
standard.  If there is a language feature you care about, please do  
take an hour or two to review the details on our wiki [3], search for  
older discussions on the mailing lists, and draft the Report changes  
you think would be necessary.  I'm looking forward to a more active  
and exciting collection of potential language changes for 2012, but it  
will only happen if you get involved.

Regards,
     Malcolm (Haskell 2011 committee chair)

[1] http://www.haskell.org/pipermail/haskell/2009-November/021750.html
[2] http://www.haskell.org/pipermail/haskell/2010-July/022189.html
[3] http://hackage.haskell.org/trac/haskell-prime/
Permalink | Reply | 5 comments |
headers
Brent Yorgey | 9 Jan 2011 18:29
Favicon
Gravatar

ANNOUNCE: Monad.Reader Issue 17

I am pleased to announce that Issue 17 of The Monad.Reader is now
available [1].

Issue 17 consists of the following three articles:

  * List Leads Off with the Letter Lambda by Douglas M. Auclair
  * The InterleaveT Abstraction: Alternative with Flexible Ordering by
    Neil Brown
  * The Reader Monad and Abstraction Elimination by Petr Pudlak

Feel free to browse the source files [2]. You can check out the entire
repository using darcs:

  darcs get http://code.haskell.org/~byorgey/TMR/Issue17

Watch for a special announcement regarding Issue 18 soon!

[1] http://themonadreader.files.wordpress.com/2011/01/issue17.pdf
[2] http://code.haskell.org/~byorgey/TMR/Issue17
Permalink | Reply | 0 comments |
headers
Anand Mitra | 11 Jan 2011 03:25
Gravatar

filesystem verification utility

Hi,

I had a requirement to generate various kinds of I/O patterns on a
filesystem and subsequently verify this. The initial version of the
program below implements a random I/O pattern with multiple threads.
Even when the number of I/O is as small as 200 and 10 concurrent
theads, the amount of memory used is huge. When I run the program it
consumes close to 1to2GB memory. Moreover the rate at which it
generates the I/O is very low which is not good for testing a
filesystem. I have used System.POSIX.IO but I tried System.IO and did
not see much difference either. I would appreciate help in identifying
ways to improve this.

{-# OPTIONS -fglasgow-exts #-}
import System.Random
import Data.List
import Monad
import System.Posix.IO
import System.Posix.Types
import Data.Time.Clock
import System.Posix.Files
import Data.Maybe
import GHC.IO.Device (SeekMode(..))
import Control.Exception
import Data.Typeable
import System
import Control.Concurrent

--myrandomRlist :: (Num t, Random t) => t -> IO [t]
--myrandomRlist x = liftM (randomRs (0,x)) newStdGen

myrandomRlist :: (Num t, Random t) => t ->t -> StdGen  ->  [t]
myrandomRlist min max seed = randomRs (min,max)  seed

data IoLoc = IoLoc {offset :: FileOffset, size::ByteCount, num::Int  }
            deriving (Show, Typeable)
instance Exception IoLoc

data Corrupt = Corrupt String IoLoc
            deriving (Show, Typeable)
instance Exception Corrupt

data FileHdr = FileHdr {fileName::FilePath, seed::StdGen,
                       minIoSize::Int, maxIoSize::Int, ioCount::Int}
              deriving (Show)

data FileIO = FileIO {fd::Fd, params::FileHdr, fileData::[IoLoc]}

genPattern :: FilePath -> IoLoc -> String
genPattern f l =
    take (read $ show $size l) (cycle  $ "(" ++ f ++ ")"  ++ "[" ++
(show (offset l)) ++ ":" ++ (show (size l)) ++ (show (num l)) ++ "]")

doHdrRead :: Fd -> IO [Char]
doHdrRead fd = do
 (str, count) <- fdRead fd 100
 return (takeWhile (\x-> not (x == '\n')) str)

doGetHdr :: Fd -> IO FileHdr
doGetHdr fd = do
 file <- doHdrRead fd
 seed <- doHdrRead fd
 minIoSize <- doHdrRead fd
 maxIoSize <- doHdrRead fd
 ioCount <- doHdrRead fd
 return (FileHdr file (read seed) (read minIoSize) (read maxIoSize)
(read ioCount))

doHdrFromFile :: FilePath -> IO FileIO
doHdrFromFile name = do
 fd <- openFd name  ReadWrite (Just ownerModes)  (OpenFileFlags
{append=False, exclusive=False, noctty=True, nonBlock=False,
trunc=False})
 hdr <- doGetHdr fd
 return (FileIO fd hdr [])

doHdrWrite :: Fd -> [Char] -> IO ByteCount
doHdrWrite fd str = do
 fdWrite fd (take 100 (str ++ "\n" ++ (cycle ['\0'])))

doWriteHdr :: Fd -> FileHdr -> IO ByteCount
doWriteHdr fd hdr = do
 doHdrWrite fd (show (fileName hdr))
 doHdrWrite fd (show (seed hdr))
 doHdrWrite fd (show (minIoSize hdr))
 doHdrWrite fd (show (maxIoSize hdr))
 doHdrWrite fd (show (ioCount hdr))

doWriteFile :: FilePath -> IO FileHdr
doWriteFile name = do
 fd <- openFd name  ReadWrite (Just ownerModes)  (OpenFileFlags
{append=False, exclusive=False, noctty=True, nonBlock=False,
trunc=True})
 seed <- newStdGen
 hdr <- return (FileHdr name seed 4096 (2*8096) 200)
 doWriteHdr fd hdr
 return hdr

overLap (IoLoc off1' sz1' num1) (IoLoc off2' sz2' num2) =
   ((off1 > off2) && (off1 < off2 +sz2)) ||((off1+sz1 >off2)
&&(off1+sz1 < off2 +sz2))
   where
     off1 = read (show off1')
     sz1 = read (show sz1')
     off2 = read (show off2')
     sz2 = read (show sz2')

genIoList1 :: [IoLoc] -> [Int] -> [Int] -> Int -> Int -> [IoLoc]

genIoList1 list offset size _ 0 =
   list
genIoList1 list offset size 0 _ =
   list

genIoList1 list (offset:os) (size:ss) count bound =
   if isNothing $ find (overLap x) list
            then genIoList1 ([x] ++ list) os ss (count - 1) (bound -1)
            else genIoList1 list os ss count (bound -1)
   where
     x = IoLoc (read (show offset)) (read(show size)) count
--      offset = (read (show offset1))
--      size = (read(show size1))

genIoList :: FileHdr -> [IoLoc]
genIoList (FileHdr name seed min max count) =
   genIoList1 []  (myrandomRlist 4000 1099511627776 seed)
(myrandomRlist min max seed) count (count*2)

doActualIo :: Fd -> IoLoc -> String -> IO ()
doActualIo fd (IoLoc off sz num) str = do
 off <- fdSeek fd AbsoluteSeek off
 fdWrite fd str
 return ()

doVerifyIo :: Fd -> IoLoc -> String -> IO ()
doVerifyIo fd (IoLoc off sz num) str = do
 off <- fdSeek fd AbsoluteSeek off
 (filedata, count) <- fdRead fd sz
 if str == filedata
    then return ()
    else throwIO (Corrupt ("Data corruption in #" ++  (take 200 str)
++ "#"  ++ (take 200 filedata))(IoLoc off sz num))

mainWrite file  = do
 hdr <- doWriteFile file
 hdrIO <- doHdrFromFile file
 iolst <- return $ genIoList hdr
 app <- return $ zip iolst (map (genPattern (fileName hdr)) iolst)
 putStrLn (fileName hdr)
 mapM (\(x,y)-> doActualIo (fd hdrIO)  x y) app
 mapM (\(x,y)-> doVerifyIo (fd hdrIO)  x y) app
 return hdr

mainVerify file = do
 hdrIO <- doHdrFromFile file
 hdr <- return (params hdrIO)
 iolst <- return $ genIoList hdr
 file <- return $ filter (\x->not ( x=='"')) (fileName hdr)
 app <- return $ zip iolst (map (genPattern file) iolst)
 putStrLn $ filter (\x->not ( x=='"')) (fileName hdr)
 mapM (\(x,y)-> doVerifyIo (fd hdrIO)  x y) app
 return hdr

main =  do
 x <- getArgs
 if (length x) == 3
   then do
     main1
   else do
     putStrLn "USAGE:\nfile-io write/verify <full-path file name>
<number of threads>  \
\\n\n\
\Simple IO load generator with write verification. This utility is designed\n\
\to generate multi-threaded IO load which will write a pattern to the file. \n\
\When this is invoked with the same parameters with the verify option \n\
\the data written will be verified.\n\
\ "

main1 = do
 [op, name, numProcs] <- getArgs
 m <- newEmptyMVar
 n <- return $read numProcs
 case op of
   "write" -> do mapM forkIO  [(fillfile (name ++ (show i)) ) m|i<-[1..n]]
   "verify" -> do mapM forkIO [(verifyfile (name ++ (show i)) ) m|i<-[1..n]]
 x <- mapM takeMVar $ take (read numProcs) $ repeat m
 putStrLn $ show $ and x

fillfile filename m = do
 mainWrite filename
 putMVar m True

verifyfile filename m = do
 mainVerify filename
 putMVar m True
Permalink | Reply | 0 comments |
headers
Anand Mitra | 11 Jan 2011 05:19
Gravatar

Re: filesystem verification utility

Based  on feedback I inferred that the huge memory usage was mostly
because of the String handling in the patern generation. To make it
more efficient I have used Data.ByteString.Lazy.Char8

but now I get the following error when I execute

stress: tmp/asdf-1: hPutBuf: illegal operation (handle is closed)
stress: tmp/asdf-3: hPutBuf: illegal operation (handle is closed)
stress: tmp/asdf-5: hPutBuf: illegal operation (handle is closed)
stress: tmp/asdf-2: hPutBuf: illegal operation (handle is closed)
stress: tmp/asdf-7: hPutBuf: illegal operation (handle is closed)
stress: tmp/asdf-10: hPutBuf: illegal operation (handle is closed)

I have explicitly remove all calls to close despite this I get this
error. I tried both version of seek the fdSeek as well as hSeek. The
documentation on hSeek had a confusing comment that "The offset i is
given in terms of 8-bit bytes"

At this point I am unable to understand how the handle is getting
explicitly closed.

{-# OPTIONS -fglasgow-exts #-}
import Data.Int
import qualified Data.ByteString.Lazy.Char8 as L
import System.Random
import Data.List
import Monad
import System.Posix.IO
import System.Posix.Types
import Data.Time.Clock
import System.Posix.Files
import Data.Maybe
import GHC.IO.Device (SeekMode(..))
import Control.Exception
import Data.Typeable
import System
import Control.Concurrent
import System.IO

--myrandomRlist :: (Num t, Random t) => t -> IO [t]
--myrandomRlist x = liftM (randomRs (0,x)) newStdGen

myrandomRlist :: (Num t, Random t) => t ->t -> StdGen  ->  [t]
myrandomRlist min max seed = randomRs (min,max)  seed

data IoLoc = IoLoc {offset ::FileOffset, size::Int, num::Int  }
             deriving (Show, Typeable)
instance Exception IoLoc

data Corrupt = Corrupt String IoLoc
             deriving (Show, Typeable)
instance Exception Corrupt

data FileHdr = FileHdr {fileName::FilePath, seed::StdGen,
                        minIoSize::Int, maxIoSize::Int, ioCount::Int}
               deriving (Show)

data FileIO = FileIO {fd::Handle, params::FileHdr, fileData::[IoLoc]}

check hdl = do
  closed <- hIsClosed hdl
  if closed
   then do
    putStrLn $ "file handle was closed" ++ (show hdl)
   else do
    return ()

genPattern :: FilePath -> IoLoc -> L.ByteString
genPattern f l =
     L.take (fromIntegral (size l)) (L.cycle  $ L.pack ("(" ++ f ++
")"  ++ "[" ++ (show (offset l)) ++ ":" ++ (show (size l)) ++ (show
(num l)) ++ "]"))

doHdrRead :: Handle -> IO [Char]
doHdrRead x = do
  fd <- handleToFd x
  (str, count) <- fdRead fd 100
  return (takeWhile (\x-> not (x == '\n')) str)

doGetHdr :: Handle -> IO FileHdr
doGetHdr fd = do
  file <- doHdrRead fd
  seed <- doHdrRead fd
  minIoSize <- doHdrRead fd
  maxIoSize <- doHdrRead fd
  ioCount <- doHdrRead fd
  return (FileHdr file (read seed) (read minIoSize) (read maxIoSize)
(read ioCount))

doHdrFromFile :: Handle -> IO FileIO
doHdrFromFile fd = do
--  fd <- openBinaryFile name  ReadWriteMode -- (Just ownerModes)
(OpenFileFlags {append=False, exclusive=False, noctty=True,
nonBlock=False, trunc=False})
  hSeek fd AbsoluteSeek 0
  hdr <- doGetHdr fd
  return (FileIO fd hdr [])

doHdrWrite :: Handle -> [Char] -> IO ()
doHdrWrite fd str = do
  hPutStr fd (take 100 (str ++ "\n" ++ (cycle ['\0'])))

doWriteHdr :: Handle -> FileHdr -> IO ()
doWriteHdr fd hdr = do
  doHdrWrite fd (show (fileName hdr))
  doHdrWrite fd (show (seed hdr))
  doHdrWrite fd (show (minIoSize hdr))
  doHdrWrite fd (show (maxIoSize hdr))
  doHdrWrite fd (show (ioCount hdr))

doWriteFile :: FilePath -> IO FileIO
doWriteFile name = do
  fd <- openBinaryFile name  ReadWriteMode -- (Just ownerModes)
(OpenFileFlags {append=False, exclusive=False, noctty=True,
nonBlock=False, trunc=True})
  seed <- newStdGen
  hdr <- return (FileHdr name seed 4096 (2*8096) 200)
  doWriteHdr fd hdr
  return (FileIO fd hdr [])

overLap (IoLoc off1' sz1' num1) (IoLoc off2' sz2' num2) =
    ((off1 > off2) && (off1 < off2 +sz2)) ||((off1+sz1 >off2)
&&(off1+sz1 < off2 +sz2))
    where
      off1 = read (show off1')
      sz1 = read (show sz1')
      off2 = read (show off2')
      sz2 = read (show sz2')

genIoList1 :: [IoLoc] -> [Int] -> [Int] -> Int -> Int -> [IoLoc]

genIoList1 list offset size _ 0 =
    list
genIoList1 list offset size 0 _ =
    list

genIoList1 list (offset:os) (size:ss) count bound =
    if isNothing $ find (overLap x) list
             then genIoList1 ([x] ++ list) os ss (count - 1) (bound -1)
             else genIoList1 list os ss count (bound -1)
    where
      x = IoLoc (read (show offset)) (read(show size)) count
--      offset = (read (show offset1))
--      size = (read(show size1))

genIoList :: FileHdr -> [IoLoc]
genIoList (FileHdr name seed min max count) =
    genIoList1 []  (myrandomRlist 4000 1099511627776 seed)
(myrandomRlist min max seed) count (count*2)

doActualIo :: Handle -> IoLoc -> L.ByteString -> IO ()
doActualIo fd (IoLoc off sz num) str = do
--  hSeek fd AbsoluteSeek off
  rfd <- (handleToFd fd)
  fdSeek  rfd AbsoluteSeek off
  L.hPut fd str
  return ()

doVerifyIo :: Handle -> IoLoc -> L.ByteString -> IO ()
doVerifyIo fd (IoLoc off sz num) str = do
--  hSeek fd AbsoluteSeek off
  rfd <- (handleToFd fd)
  fdSeek rfd AbsoluteSeek off
  filedata  <- L.hGet fd sz
  if str == filedata
     then return ()
     else throwIO (Corrupt ("Data corruption in #" ++  (take 200
(L.unpack str)) ++ "#"  ++ (take 200 (L.unpack filedata)))(IoLoc off
sz num))

mainWrite file  = do
  (FileIO hd _ _) <- doWriteFile file
  hdrIO <- doHdrFromFile hd
  check hd
  (FileIO _ hdr _) <- return hdrIO
  check hd
  iolst <- return $ genIoList hdr
  app <- return $ zip iolst (map (genPattern (fileName hdr)) iolst)
  putStrLn (fileName hdr)
  mapM (\(x,y)-> doActualIo (fd hdrIO)  x y) app
  mapM (\(x,y)-> doVerifyIo (fd hdrIO)  x y) app
--  hClose hd
  return hdr

mainVerify file = do
  hd <- openBinaryFile file  ReadWriteMode
  hdrIO <- doHdrFromFile hd
  hdr <- return (params hdrIO)
  iolst <- return $ genIoList hdr
  file <- return $ filter (\x->not ( x=='"')) (fileName hdr)
  app <- return $ zip iolst (map (genPattern file) iolst)
  putStrLn $ filter (\x->not ( x=='"')) (fileName hdr)
  mapM (\(x,y)-> doVerifyIo (fd hdrIO)  x y) app
--  hClose hd
  return hdr

main =  do
  x <- getArgs
  if (length x) == 3
    then do
      main1
    else do
      putStrLn "USAGE:\nfile-io write/verify <full-path file name>
<number of threads>  \
\\n\n\
\Simple IO load generator with write verification. This utility is designed\n\
\to generate multi-threaded IO load which will write a pattern to the file. \n\
\When this is invoked with the same parameters with the verify option \n\
\the data written will be verified.\n\
\ "

main1 = do
  [op, name, numProcs] <- getArgs
  m <- newEmptyMVar
  n <- return $read numProcs
  case op of
    "write" -> do mapM forkIO  [(fillfile (name ++ (show i)) ) m|i<-[1..n]]
    "verify" -> do mapM forkIO [(verifyfile (name ++ (show i)) ) m|i<-[1..n]]
  x <- mapM takeMVar $ take (read numProcs) $ repeat m
  putStrLn $ show $ and x

fillfile filename m = do
  mainWrite filename
  putMVar m True

verifyfile filename m = do
  mainVerify filename
  putMVar m True

On Tue, Jan 11, 2011 at 1:02 AM, Anand Mitra <mitra <at> kqinfotech.com> wrote:
> Hi,
>
> I had a requirement to generate various kinds of I/O patterns on a
> filesystem and subsequently verify this. The initial version of the
> program below implements a random I/O pattern with multiple threads.
> Even when the number of I/O is as small as 200 and 10 concurrent
> theads, the amount of memory used is huge. When I run the program it
> consumes close to 1to2GB memory. Moreover the rate at which it
> generates the I/O is very low which is not good for testing a
> filesystem. I have used System.POSIX.IO but I tried System.IO and did
> not see much difference either. I would appreciate help in identifying
> ways to improve this.
>
>
Permalink | Reply | 2 comments |

Gmane