Mysql – Insert Speeds for large batches

In my application, my INSERTs seem to be taking a major chunk of the time. I have a large number of objects in memory (~40-50,000) which i want to insert into a table.

Lets take a sample table

CREATE TABLE bill (
id BIGINT(20) PRIMARY KEY,
amount INT(11) DEFAULT 0,
bill_date DATETIME DEFAULT NOW(),
INDEX (bill_date)
) ENGINE=InnoDB

Taking 3 rows as my batch size, the following are the approaches i could think of for inserting

Approach 1 – construct and fire 3 raw inserts

INSERT INTO bill (amount, bill_date) VALUES (10, '2012-01-01 00:00:00');
INSERT INTO bill (amount, bill_date) VALUES (20, '2012-01-02 00:00:00');
INSERT INTO bill (amount, bill_date) VALUES (40, '2013-02-05 00:00:00');

Approach 2 – clubbing the values into 1 query

INSERT INTO bill (amount, bill_date) VALUES 
(10, '2012-01-01 00:00:00'),
(20, '2012-01-02 00:00:00'),
(40, '2013-02-05 00:00:00');

Approach 3 – fire this query 1 time passing 6 parameters

INSERT INTO bill (amount, bill_date) VALUES 
(?, ?), (?, ?), (?, ?);

Approach 4 – Fire this prepared query 3 times changing the 2 parameters each time

INSERT INTO bill (amount, bill_date) VALUES (?, ?);

Any other approaches are welcome.

My question is

What is the quickest way to make multiple inserts in a table?

I have read this link on mysql insert speed and this guide to JDBC programming, but i'm not able to come to a conclusion.

My case –

Currently my table has ~ 20 columns, most of which are numbers, with a couple of varchar(60) and 1 text column. Mysql version 5.5.
Running on INNODB and has 1 index on Integer primary keys.
All the queries run in transaction.

I construct my queries from Java and use Spring JDBC to run the queries.

I am currently following Approach 3, It is taking around 10 seconds for 20,000 inserts to an empty table, not including the time it takes to construct the query.

To keep things in perspective, its taking 100-200 millis to fetch the data from the table.

Is there something i am missing?
How do i make the inserts faster?