Optimizing Huffman, part 2

In spite of the improvements made to the Huffman program’s use of I/O functions in the previous post, it’s fairly clear that more can be done.  In particular, looking at the profiles for encoding and decoding, the fgetc/fputc pair still account for a significant amount of the program’s runtime.  While we succeeded in getting rid of them for reading and writing normal (unencoded) data, we still used them for the encoded data.  It turns out that this isn’t too hard to fix either.

simplehuffman3.c implements this idea.

Continue reading

Profiling and optimizing Huffman

The Huffman example I posted last month has the virtue of being quite simple.  On the flip-side, it has some room for improvement, particularly when it comes to performance.

Of course no less a computer scientist than Don Knuth once said that “Premature Optimization is the root of all evil.”  So it makes sense to look for the most obvious bottlenecks first.

simplehuffman2.c is the optimized version.  A description of the approach follows.

Continue reading

A simple Huffman implementation

Huffman encoding uses some interesting insights about data to achieve compression.  It’s reasonably simple, and exposes some interesting questions about data representation and optimization.

simplehuffman.c – (300 lines of C) is a program I wrote in an afternoon to do Huffman encoding and decoding of files.  It will work on any type of file and can compress and decompress a 15MB text file in under 2 seconds on current hardware.

Continue reading

The Coast to Coast Walk

P6207470 Across England – Walking Wainwright’s Coast to Coast route

Preparations – What we did to prepare for the walk

Day 0 – Getting to Kirkby Stephen – In which we all somehow manage to arrive in Kirkby Stephen in time for dinner.

Day 1 – St. Bees to Ennerdale Bridge – In which we set off on our journey only to immediately get lost. Also: an introduction to two English institutions: the pub and the weather, and a lesson in country living.

Day 2 – Ennerdale Bridge to Longthwaite – In which we continue our way across the Lake District and make a worthwhile detour up into the hills in search of adventure. Also: getting an understanding for the youth hostel system.

Day 3 – Longthwaite to Grasmere – In which we are thoroughly drenched en route to Wordsworth’s home and celebrate the birthday of our guides in style.

Day 4 – Grasmere to Patterdale – In which a complete absence of rain provides the perfect excuse to visit England’s third highest mountain and descend via the aptly named ‘Striding Edge.’ Also: experiencing a proper evening in the pub.

Day 5 – Patterdale to Shap – In which we ascend Kidsty Pike without being able to see it (or much of anything else) before leaving the hills of the Lake District for good. Also: admiring the handiwork of King Henry VIII and learning a valuable lesson about sheep.

Day 6 – Shap to Kirkby Stephen – In which we enjoy the benefits of a cream tea in the morning and a massive downpour in the evening crossing the middle of England.

Day 7 – Kirkby Stephen to Keld – In which a wet day is made considerably soggier thanks to the presence of numerous bogs and we encounter the happiest farm in England. Also: a brief stop at Nine Standard Riggs.

Day 8 – Keld to Reeth – In which we cross the Pennines and pass numerous relics of Britain’s mining past. Also: what to do when the afternoon proves rain-free.

Day 9 – Reeth to Richmond – In which a short leg ends in our first encounter with a real city. Also: trying out England’s new national dish at dinner.

Day 10 – Richmond to Oaktree Hill – In which we miss the rainy weather and sweat our way across the lowlands. Also: learning how to fill Sunday afternoon in a really small town.

Day 11 – Oaktree Hill to Clay Bank Top (Chop Gate) – In which we continue to bake even while leaving the lowlands for the moors. Also: the incredible friendliness of folks in the countryside and the case for leaving the urban grind.

Day 12 – Clay Bank Top to Blakey Ridge (Rosedale Abbey) – In which the weather mercifully cools off allowing us to traverse the Yorkshire Moors in relative comfort. Also: the peculiar story of the grouse, the gentry and the moors.

Day 13 – Blakey Ridge to Grosmont – In which we catch numerous glimpses of the ocean descending off the moors and are treated to some of England’s finest villages. Also: learning a bit about British railroads.

Day 14 – Grosmont to Robin’s Hood Bay (Kirkby Stephen) – In which we conclude our walk with a stretch along the rugged coast and help move England slightly eastward. Also: the best vegetarian dinner in Cumbria and swapping stories with 6 other hikers on the same hike.

Day 14 + 1 – Conclusion – In which we find ourselves in York and discover the difference between being a tourist and being a hiker. Also: the nuisances of luggage.

Day 14+1 – Conclusion

DSC 7423

Thursday June 30 – Concluding

Our journey did not in truth end at Robin’s Hood Bay. First, there was the matter of returning to Kirkby Stephen. This we did thanks to the luggage service’s bus. After a few hours of exploring Robin’s Hood Bay, including a pause at the Victoria Inn pub to celebrate, we caught the bus around 4PM. The bus driver was a talkative fellow, so I learned a fair amount throughout our 2 hour drive to Kirkby Stephen. He was also quite skillful, maneuvering the van up and down narrow roads and streets. Despite it being almost rush hour, we saw little traffic save on one major motorway.

To celebrate the successful completion of the Coast to Coast walk, we decided to have dinner at the Croglin Castle, a restaurant in Kirkby Stephen known for its vegetarian shepherd’s pie. The fact that establishment had its own brewery was merely an additional incentive! After an excellent dinner (everybody had the same dish – shepherd’s pie), we were greeted by some familiar voices – 6 members of the same hiking group in the bay area were also doing the Coast to Coast walk too, but 8 days after us, so they were passing through Kirkby Stephen on the way to Keld. They had gone as part of a tour, and apparently had had much drier weather than us. We exchanged stories until quite late.

Friday June 31 – Epilogue

The next morning was not particularly relaxed. In addition to repacking our luggage (we’d left a suitcase in Kirkby Stephen the first time through), we had to figure out our next step. Michelle and Mark were heading back to London. Chris and Bridget were going off to see a bit more of the Lake District. After some back and forth, the remaining 3 of us agreed to go to York in the hopes of visiting a scenic, but still smallish, city. Making rail arrangements proved complicated too, but at length the taxi deposited us at the station, Chris and Bridget said goodbye, and we caught the same train we’d taken on our first day in England, only this time back toward Leeds.

The train ride was scenic, as it had been on our arrival. Unfortunately, we were now saddled with a full collection of luggage, which hampered movement considerably. At Leeds, I got tickets to York, and when the express train to York arrived, we had to quickly load ourselves and our luggage into it. We nearly left behind several pieces of baggage. Unloading in York was also hurried. Using a payphone, I managed to find a hotel, but getting there again required the assistance of a taxi. A day before the one mile walk would have been a pleasant diversion, but now it required a car to complete. It was a relief to drop the luggage at Astley House, and venture out into the town unencumbered.

York showed itself to be, as advertised, a very pleasant old city of manageable size. Without a set end-point determining our movements, it was difficult to decide what to do, so we did a fair amount of meandering through the old town. After two weeks spent mostly in towns that could be walked across in 5 minutes, we found ourselves beginning to get lost in the maze of small streets and intersections. The most interesting place we did visit was the railroad museum, which included some magnificent old steam engines as well as a great deal of history. This was enough to leave us hungry, and we had dinner at an Italian restaurant.

When we had finished dinner and returned to the hotel, there was the question of what to do for the following day. Again I thought back to our walk, and somehow it did feel that in spite of the difficulties of finding, following and completing the route, life looked more complicated now that we were no longer walkers on the way to the next town, but tourists, looking for something interesting, but not sure exactly what that something was.

Day 14 – Grosmont to Robin’s Hood Bay

DSC 7186

Thursday June 30 – Grosmont to Robin’s Hood Bay

Getting up at 6AM was surprisingly not so difficult. It helped that it was quite light outside, and appeared to be the beginning of a beautiful day. It also helped that the steam train had already made its first jaunt through town. The proprietor was true to his word, and we had a good breakfast before setting out up the steep hill to Littlebeck.

In an effort to avoid the sort of miscalculations that had led us astray on the first day of the trip, I kept both map and GPS handy, and things on the ground seemed to more or less accord with the map. The hill was quite steep, but after 40 minutes or so, we had crested the top of the moor and were being treated to the sounds of the busy A169 highway. We only had to walk alongside the highway for ¼ mile but it was enough. Then we followed a narrow trail, joining the main road to Littlebeck not too far on. We were just beginning to wonder which farm we were supposed to pause at when we saw Michelle and Mark. We continued on and found Bridget and Chris at the bottom of the hill, by the creek.

The next bit of trail paralleled the creek, taking us along a wooded hillside, past a cave known as the hermitage, and down to bridge. Across the bridge we found the charmingly named ‘Midge Hall’. The route then continued through the wood, returned to the east bank of the creek, and eventually emerged near a small car park. Here we returned to the road, climbing up a hill past several farms including one with a very vocal watchdog, and cresting with a view that extended all the way out to the ocean and the seaside resort of Whitby.

After a section next to the B1416, we crossed and began to head directly toward the sea. It was a lot further than it looked, and the moors gave way to cultivated fields. Soon our trail was swallowed up by tall hedges on either side. We meandered in this fashion for a fair distance, finally emerging near the town of Hawsker. We took a short rest in the center of the town on some well-positioned benches, and watched a driver-in-training navigating the turns and roundabouts of the main road through the town.

Our trail then proceeded to take us down a narrow country lane that somehow opened up on a massive RV park. Admittedly it seemed a rather nice RV park, being quite clean and offering an excellent view of the ocean, but I couldn’t help feeling that it was out of place. Still, we made our way through it, and a few hundred yards further along we reached the sea.

Or rather, we reached the cliffs. The sea was there all right, a few hundred feet below us. The trail took us south, following the contours of the bluffs. After a few minutes, as if on cue, the darkened section of sky proceeded to expand on us, and it started to get wet. After a pause to put on jackets, we continued.

The last few miles of the coast to coast trail kept to the bluffs. We had views out over the ocean, but also inland at the nearby farms. Some of the fields above the ocean had cows in them. We passed a good many other walkers, but most seemed to be just out for a pleasant stroll.

At length, the town of Robin’s Hood Bay appeared before us on the coast. The trail deposited us on a street surrounded by well-maintained vacation houses, and this we followed down into the center of town. We found numerous groups of tourists, many of them schoolchildren making their way down to or up from the beach. We followed the downward group and at about 2PM we crossed a small street onto the sand. Those of us with stones from the west coast (Bridget, Chris, Michelle and Mark) deposited them in the water. We took a group photo. And that was the Coast to Coast walk.

Day 13 – Rosedale Abbey to Grosmont

DSC 6810

Wednesday June 29 – High Blakey to Grosmont (14.5 miles)

Breakfast was in a beautiful dining room, looking out across the garden at what appeared to be a beautiful clear day. It was not particularly warm either when we were dropped off at the top of the moor by the Lion Inn.

The first stretch of our walk followed the road, and we were a bit nonplussed by some of the drivers whizzing about at high speeds. I can only imagine how the poor sheep felt. We paused at ‘Fat Betty’, an ancient stone landmark, and left an offering of travel bars, per the tradition. A little further on, we caught our first glimpse of the North Sea.

We took around an hour to reach the end of Blake Moor. Here we left the road, and began to descend mostly keeping to the ridgeline. The clouds had begun to darken again, but we had a nice view out over the valley of the river Esk. We passed over a few hills, with views on either side, and then the rain began. So we put on our rain gear. As soon as the rain gear was on, it was scarcely 5 minutes before the rain stopped again.

We ate lunch sitting on a little hill looking out over the Rosedale valley to the south of us. After lunch, we resumed our downward plod. Another hour or so and we arrived in Glaisdale, a village officially ranked as among the best in England. It seemed a pleasant place, although we somehow missed the grocery store. We did however meet a number of colorful, if largely silent inhabitants: the wombles. We found these curious looking characters dressed in all manner of different costumes, with one seated or perched in front of almost every house. We also found a few human inhabitants, including a policeman who seemed to be in the process of teaching some youngsters the protocols involved in riding a bike.

From Glaisdale we descended to the tiny hamlet of Arncliffe Arms. There we passed a small train station that seemed deserted, save for an official looking sign warning that anybody who left the gate to the station open would be on the line for 1,000 quid. We made sure to close the gate after taking our photos.

Continuing on, we followed a path into the woods, which we had entirely to ourselves. It was fairly dark under the trees and after half an hour it was hard to tell where we had go to, but we emerged on a road, and followed it downhill to the town of Egton Bridge. Here we crossed the River Esk on stepping-stones, a task made easier by the careful placement of the stones and the calm, slow flow of the river. We were in a sufficient hurry not to stop at St. Hedda’s church and look at the remains of Nicholas the martyr (another casualty of the English reformation), and proceeded directly through the remains of an old estate that currently seemed to be mainly a home to a number of donkeys and some farm equipment.

Around 4PM, we reached Grosmont. After passing down the main street, we stopped at the Station Pub for a drink, and admired the heritage steam train that passed along the railroad track in the center of the town. But the weather was turning and Bridget, Chris, Michelle and Mark all had another 3 miles left for the day, so we said goodbye and set about checking in to our bed and breakfast. The rain came down heavily for the next twenty minutes, then disappeared for the rest of the day.

We soon discovered that Grosmont was a much smaller town than had initially appeared when we found the only grocery store had closed at 5PM. We wandered down to the railroad museum just outside of the town, but that too was closed for the day, so we returned to the pub to settle the matter of dinner. Inside, we met a group we’d seen 3 days before on the trail. This was their second time doing the coast-to-coast route, and they were enjoying it every bit as much as their first one.

After dinner we returned to our B&B. The proprietor we soon learned was a former railroad engineer and he had a wealth of information to tell us about his time on the railroad, as well as his adventures cycling around England and the continent, which even a bout with cancer had not stopped. We had a good chat before going to bed. Upon the news that we intended to be up at 6AM, he said that he’d be up a 5:30 to prepare breakfast. We insisted this wouldn’t be necessary, but he said it was nothing he hadn’t done many times before, while working on the railroad.

Day 12 – Chop Gate to Rosedale Abbey

DSC 6693

Tuesday June 28 – Carlton Bank to High Blakey (11.0 miles)

For once, I was pleased to see that it was overcast when I went down for breakfast. Despite being the only guest, I received all the benefits of good English breakfast including some amazing slow-roasted tomatoes and excellent sausages. So fortified, he deposited me back at the same parking from which he’d picked me up the night before. The others had recently arrived and were still adjusting their gear. It was 9:30AM.

From the café, our route was again up as we climbed a succession of 3 separate hills, each more substantial than the next. The clouds kept things cool for the ascent although it did limit our views out across the moors and the escarpment. The trail became surprisingly rocky in a few sections. At one point we encountered a group of schoolchildren in outdoors gear, complete with helmets, heading down the trail. We saw another group in the process of climbing up the escarpment. They looked to be having fun.

Aside from bushed and the occasional berry, the moors did not have many features. We saw a few sheep here and there, but not the large flocks we’d seen grazing earlier in the grasslands. From the top of Clay Bank, the most substantial of the hills, we had a fairly wide view across Yorkshire, both north toward Middlesbrough and east across the moors. After the schoolchildren, we did not see anybody else on the trail.

We took a fairly brief lunchbreak where the trail met an old railroad line that had since been demolished. Continuing along the top of the moors, we went more or less due east. Mark’s feet were bothering him somewhat, and we were all pleased to finally have a view of the Lion Inn when we turned a corner around 3PM. Somehow the walk ended up seeming longer than the 11 miles it was supposed to be.

At the Lion Inn, we warmed up (it had become quite cool), rested our feet, and around 4PM the proprietor of our guesthouse came by to fetch Bob, Sassan and I. He was very friendly, and even agreed that he could bring us back up in the evening to join the others for dinner. The drive down to Rosedale Abbey was pleasant and informative, but a little jarring, for the road twisted and turned around to the point that I completely lost my sense of direction. The August Guesthouse was a well-appointed building slightly above the level of the town at the bottom of the alley. We were all happy to have a quiet afternoon to rest and recuperate.

We caught a ride back up to the Lion around 7PM. The others were comfortably ensconced at their B&B across the road. The special of the night was the Stilton Cheese melt. Having missed out on the previous night’s special, we let Mark order first. Naturally, there was only enough cheese for 2 people to order the dish. After dinner, we went outside and saw the ending of a gorgeous sunset. Naturally, my appropriate camera lens was back at the hotel. We enjoyed a fairly restful night.

Day 11 – Oaktree Hill to Chop Gate

P6278209

Monday June 27 – Oaktree Hill to Carlton Bank (16.5 miles)

When we got up in the morning it was cooler. We enjoyed a slightly simpler breakfast than the usual, but still about twice as large as one would usually have at home. However by the time we were ready to leave, it was again looking to be an unpleasantly hot day. We said goodbye to the Canadians, to Farmer John, and to his friendly collie, and resumed our eastward trek a little after 9AM.

The trail was much the same as the previous day. We criscrossed fields of grain and grass, occasionally following roads and even more occasionally seeing other folks. Around an hour into our walk we crossed a railroad track at a level crossing. The train came through 3 minutes later. The temperature rose to an unpleasant level.

Around 11AM we reached the A171 highway. Unlike our previous encounters with busy roads, this one offered no option but to run across. Fortunately it was a divided road with a median and after a few patient minutes we were on the other side. There we found ourselves in the town Ingleby Arncliffe. At the Blue Bell Inn, we all got cool drinks, then continued on.

We crossed a second highway on the other side of the town, before beginning our first real ascent since before Reeth. Chris wanted to visit the Mt. Grace Priory, another victim of Henry VIII, and Bob, Sassan and I joined. The other continued straight ahead, promising to wait at the top of the hill, near a large aerial antenna.

The priory proved an extensive establishment. We took a quick look at the museum, then headed outside to have our lunch. Apparently thanks to a lord in the area who had purchased the place at auction from the crown, it had avoided the typical destruction of other similar buildings (most of the monks were not as lucky – they were executed). We wandered the grounds including a reconstructed unit similar to the dozens that had housed the monks in bygone days.

Still, we didn’t want to be left behind, so around 1:30PM we left to continue climbing the next hill. We began in the woods but soon emerged into the open. The views were compromised by a thick haze but at least the temperature was beginning to drop. We discovered numerous patches of some type of blue berry. They were excellent. We met the others just beyond the antenna.

The Yorkshire moors are a series of broad, woodless hills. We were on the northwest edge of the moors as we proceeded along our route which had now joined another well-known long-distance trek: the Cleveland Way. The trail dropped down, reascended, dropped down again, and after a lengthy period in the woods, began our final ascent of the day. The fading heat helped a bit, but it was still a hefty climb. In one field, I saw my first hare – a giant rabbit bounding along with seemingly inexhaustible energy.

Once we reached the top of the moor again, we again had a view. We more or less skirted an escarpment that marked the western boundary of the moors. After a fair distance on top of Carlton Bank, we spotted a large building. This turned out to be a lodge for a former glider club. Given the height of the escarpment it wasn’t hard to see why they’d chosen this spot to put the club. We were all happy when caught sight of a road, and after a short descent crossed it and arrived at Lordstone’s Café.

After a brief wait cooling off outside the cafe, the proprietors of the hotels where we were staying drove up to give us a lift. The ride down to the village of Chop Gate was not too far, but I was very happy not to have to walk it. Owing to complications with booking, everybody but me stayed in one B&B and I stayed in the other. This proved not a bad thing at all for the proprietor where I stayed was a very friendly and well-traveled fellow and was happy to explain all about the local scene. In addition to operating a B&B in the English countryside, he had also been a royal marine and policeman in London, and had hike part of the Pacific Crest Trail in California.

Once I had deposited my bags and showered, I was introduced to their cows and sheep. Then I headed down to the Buck Inn to see the rest of the group for dinner. Per recommendation, I had venison. So did several other people, but unfortunately they ran out by the time Mark ordered. So he got stuck with casserole instead! I was happy to go to bed shortly after dinner.

Day 10 – Richmond to Oaktree Hill

DSC 6446

Sunday June 26 – Richmond to Oaktree Hill (16.5 miles)

The dining room at the Frenchgate Guesthouse offered us a great view of the nearby valley. We enjoyed a typically extensive breakfast. When I showed my camera, the proprietor suggested I take a photo from their balcony, but not actually go out and stand on the balcony. Apparently construction began, but was halted due to permit issues, so the view was there, but the support was not.

We left the hotel around 9AM and descended down to the riverbank. Not only was the sky free of clouds but the temperature was already quite warm. It would only get warmer as the day wore on. After an hour we reached another site of ruins. Easby Abbey was another victim of Henry VIII’s war with the Catholic Church. Like Shap it was relatively well-preserved, with numerous towers and walls remaining of what had once been a major medieval center.

We crossed the river shortly past the abbey, continuing on the other bank. The trail took us along the edge of numerous barley, wheat and alfalfa fields. Agriculture rather than livestock seemed to predominate in this valley. We missed the trail near the Catterick bridge, but recovered it and crossed alongside a bona fide traffic jam. It was even hotter when we left the river near Great Langton. We stopped in a field for lunch.

After lunch the trail was much the same, passing between fields of different crops and wending its way past one farm and then another. Despite the trail being mostly flat, it was dreadfully hot and what shade we had was quite inadequate. When we wandered in to the small town of Danby Wiske at 3:30PM, everybody was keen on finding a place indoors and something cool to drink.

These things we found at the White Swan pub. As our destination did not have any place to get dinner, and as the pub was the only establishment open on Sunday afternoon, we decided to stay there and resume our walk after dinner. Mark was particularly in favor of this option, and proceeded to work his way through 4 or 5 pints before dinner was served around 7PM. Everybody had asked for extra vegetables, and for once, the kitchen delivered. We were unable to actually finish all of them, despite a valiant effort.

Around 8:30PM, Mark decided it was a good time to get going. We paid the considerable tab, repossessed our backpacks and slowly began our trudge toward Oaktree Hill. Despite the extra pints he had had with dinner, Mark led us on what proved to be the most direct route. Unfortunately, some of the trails, while well marked on the map, were heavily overgrown, so we were forced to beat our way through underbrush, cross a disintegrating bridge, and backtrack through a large barley field before we found a workable way through. Still, we got to enjoy the sunset on the trail and arrived at Lovesome Hill farm, none the worse for the wear.

Our farm accommodations were basic but sufficient. The main problem was simply the heat. We discovered that among our fellow guests was a group of Canadians touring the English countryside. They mentioned a 2000+ mile trail following old Canadian rail lines. I promised myself I’d think at least twice before I considered any hike of more than 3 days again.