4

Is there a fast, low-garbage way to do it? I can't just do simple modulus arithmetic since that doesn't account for leap seconds and other date/time funny business.

Thomas Johnson
  • 10,776
  • 18
  • 60
  • 98

6 Answers6

13

I've figured out how to deal with leap years in integer arithmetic and implemented a converter from seconds since Epoch to date/time (it never gives you more than 59 seconds, though). The below C code should be very easy to port to Java.

#include <string.h>
#include <time.h>

typedef unsigned uint;
typedef unsigned long long uint64;

struct tm* SecondsSinceEpochToDateTime(struct tm* pTm, uint64 SecondsSinceEpoch)
{
  uint64 sec;
  uint quadricentennials, centennials, quadrennials, annuals/*1-ennial?*/;
  uint year, leap;
  uint yday, hour, min;
  uint month, mday, wday;
  static const uint daysSinceJan1st[2][13]=
  {
    {0,31,59,90,120,151,181,212,243,273,304,334,365}, // 365 days, non-leap
    {0,31,60,91,121,152,182,213,244,274,305,335,366}  // 366 days, leap
  };
/*
  400 years:

  1st hundred, starting immediately after a leap year that's a multiple of 400:
  n n n l  \
  n n n l   } 24 times
  ...      /
  n n n l /
  n n n n

  2nd hundred:
  n n n l  \
  n n n l   } 24 times
  ...      /
  n n n l /
  n n n n

  3rd hundred:
  n n n l  \
  n n n l   } 24 times
  ...      /
  n n n l /
  n n n n

  4th hundred:
  n n n l  \
  n n n l   } 24 times
  ...      /
  n n n l /
  n n n L <- 97'th leap year every 400 years
*/

  // Re-bias from 1970 to 1601:
  // 1970 - 1601 = 369 = 3*100 + 17*4 + 1 years (incl. 89 leap days) =
  // (3*100*(365+24/100) + 17*4*(365+1/4) + 1*365)*24*3600 seconds
  sec = SecondsSinceEpoch + 11644473600LL;

  wday = (uint)((sec / 86400 + 1) % 7); // day of week

  // Remove multiples of 400 years (incl. 97 leap days)
  quadricentennials = (uint)(sec / 12622780800ULL); // 400*365.2425*24*3600
  sec %= 12622780800ULL;

  // Remove multiples of 100 years (incl. 24 leap days), can't be more than 3
  // (because multiples of 4*100=400 years (incl. leap days) have been removed)
  centennials = (uint)(sec / 3155673600ULL); // 100*(365+24/100)*24*3600
  if (centennials > 3)
  {
    centennials = 3;
  }
  sec -= centennials * 3155673600ULL;

  // Remove multiples of 4 years (incl. 1 leap day), can't be more than 24
  // (because multiples of 25*4=100 years (incl. leap days) have been removed)
  quadrennials = (uint)(sec / 126230400); // 4*(365+1/4)*24*3600
  if (quadrennials > 24)
  {
    quadrennials = 24;
  }
  sec -= quadrennials * 126230400ULL;

  // Remove multiples of years (incl. 0 leap days), can't be more than 3
  // (because multiples of 4 years (incl. leap days) have been removed)
  annuals = (uint)(sec / 31536000); // 365*24*3600
  if (annuals > 3)
  {
    annuals = 3;
  }
  sec -= annuals * 31536000ULL;

  // Calculate the year and find out if it's leap
  year = 1601 + quadricentennials * 400 + centennials * 100 + quadrennials * 4 + annuals;
  leap = !(year % 4) && (year % 100 || !(year % 400));

  // Calculate the day of the year and the time
  yday = sec / 86400;
  sec %= 86400;
  hour = sec / 3600;
  sec %= 3600;
  min = sec / 60;
  sec %= 60;

  // Calculate the month
  for (mday = month = 1; month < 13; month++)
  {
    if (yday < daysSinceJan1st[leap][month])
    {
      mday += yday - daysSinceJan1st[leap][month - 1];
      break;
    }
  }

  // Fill in C's "struct tm"
  memset(pTm, 0, sizeof(*pTm));
  pTm->tm_sec = sec;          // [0,59]
  pTm->tm_min = min;          // [0,59]
  pTm->tm_hour = hour;        // [0,23]
  pTm->tm_mday = mday;        // [1,31]  (day of month)
  pTm->tm_mon = month - 1;    // [0,11]  (month)
  pTm->tm_year = year - 1900; // 70+     (year since 1900)
  pTm->tm_wday = wday;        // [0,6]   (day since Sunday AKA day of week)
  pTm->tm_yday = yday;        // [0,365] (day since January 1st AKA day of year)
  pTm->tm_isdst = -1;         // daylight saving time flag

  return pTm;
}

See a test run at ideone.

Andre Kampling
  • 5,476
  • 2
  • 20
  • 47
Alexey Frunze
  • 61,140
  • 12
  • 83
  • 180
  • Nice work! This is exactly what I needed. To confirm, the checks for clamping centennials/quadrennials/annuals were just for your sanity during dev right? It looks to me that mathematically these can never happen. Also after each you do `sec -= duration * secs`, which is equivalent to using `%` - which you do use for `quadricentennials`, just a minor inconsistency. I would choose either `-=` or `%=` for them all. – David Jul 15 '12 at 13:32
  • @Dave They are for sanity, yes, but most importantly for correctness. :) Try removing them and rerunning the small test code at ideone. Notice how suddenly 978307199="Sun Dec 31 23:59:59 2000" becomes 978307199="Sun Jan 1 23:59:59 2001", but 978307199+1="Mon Jan 1 00:00:00 2001" stays the same. Last second of 2000 is less than 400 years away from 1/1/1601 (right? just compare the years) but is more than 4*100 years away from 1/1/1601 (365.24-days-long years, that is). By removing the first clamp you will not properly account for the 97th leap year in every 400 years, our case here. – Alexey Frunze Jul 15 '12 at 19:39
  • On my 32 bit build I had to changed one line. This line: `sec = SecondsSinceEpoch + 11644473600;` must be `sec = SecondsSinceEpoch + 11644473600LL;`. Note the `LL` as it would fail on 32 bit builds. Sure it will just work if the `long long` types are 64 bit wide. – Andre Kampling Jul 18 '17 at 15:56
  • Thanks! Your 64-bit time variable and this conversion code helped me in my Time Machine project. Now I can time travel much farther than just 70 years back and forward. I have adapted it just a bit for Arduino and it runs perfectly. – Pavel Anni Apr 30 '19 at 13:25
4

I can't just do simple modulus arithmetic since that doesn't account for leap seconds and other date/time funny business.

Java doesn't account for leap seconds in general - or rather, officially that's up to the platform, but I don't believe it's implemented in any of the common production platforms. Are you sure you need to account for leap seconds? If you do, you should be able to do a simple table-based lookup of the number of seconds to add or remove, depending on what your data source is and what you want it to reflect.

As for "other date/time funny business" - I don't think there is any funny business for this particular calculation. Time zones are irrelevant in terms of elapsed time since the epoch, for example.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • Time zones are irrelevant for seconds since the epoch, but not irrelevant when converting to local HH:MM:SS time. Still, it's just a constant offset, so not a big deal. – Thomas Johnson Jun 25 '12 at 12:04
  • @user939259: I assumed you meant "hours, minutes, seconds" since the epoch... your question is very unclear. If you meant you want to convert a timestamp to a local time, then you can use `java.util.Date` and `java.util.Calendar`, or preferrably Joda Time. – Jon Skeet Jun 25 '12 at 12:38
2

Assuming with "epoch" you mean 01-01-1970, 00:00:00 GMT:

long secondsSinceEpoch = ...;

// The constructor of Date expects milliseconds
// since 01-01-1970, 00:00:00 GMT
Date date = new Date(secondsSinceEpoch * 1000L);

DateFormat df = new SimpleDateFormat("dd/MM/yyyy");
System.out.println(df.format(date)); 
Jesper
  • 202,709
  • 46
  • 318
  • 350
  • @MarkoTopolnik Explain? The only thing you're creating is a `Date` object (disregarding the formatting with a `SimpleDateFormat`). That's not very expensive. – Jesper Jun 25 '12 at 11:43
  • Date, SimpleDateFormat, the internals of both. That's not that little and the result is still a String instead of a tuple of numbers. Plus OP said he only wants HMS, maybe he meant hours since epoch? It's not clear. – Marko Topolnik Jun 25 '12 at 11:45
1
Calendar = Calendar.getInstance();
calendar.setTimeInMillis(secondsSinceTheEpoch*1000);
Christoffer Hammarström
  • 27,242
  • 4
  • 49
  • 58
1

This is a fast, zero-garbage solution. It is of key importance not to create a new instance of Calendar on each call because it's quite a heavyweight object, taking 448 bytes of heap and almost a microsecond to initialize (Java 6, 64-bit HotSpot, OS X).

HmsCalculator is intended for use from a single thread (each thread must use a different instance).

public class HmsCalculator
{
  private final Calendar c = Calendar.getInstance();

  public Hms toHms(long t) { return toHms(t, new Hms()); }
  public Hms toHms(long t, Hms hms) {
    c.setTimeInMillis(t*1000);
    return hms.init(c);
  }
  public static class Hms {
    public int h, m, s;
    private Hms init(Calendar c) {
      h = c.get(HOUR_OF_DAY); m = c.get(MINUTE); s = c.get(SECOND);
      return this;
    }
    public String toString() { return String.format("%02d:%02d:%02d",h,m,s); }
  }

  public static void main(String[] args) {
    System.out.println(new HmsCalculator().toHms(
       System.currentTimeMillis()/1000));
  }
}

P.S. I didn't paste all those static imports (boring).

Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
  • @ChristofferHammarström Now we all know you didn't read the last sentence of the answer :) – Marko Topolnik Jun 26 '12 at 10:41
  • Oh, right. It's was apparently non-obvious, so i fixed it instead, i hope you don't mind. – Christoffer Hammarström Jun 26 '12 at 10:46
  • I do indeed mind as I specifically wrote that code to satisfy OP's requirement of being low-garbage. He didn't mention thread-safe. Roll it back, please. – Marko Topolnik Jun 26 '12 at 10:48
  • I don't know, I never said any such thing. My solution is low-garbage -- zero-garbage, to be exact, if you don't count the returned array. Yours obviously isn't. – Marko Topolnik Jun 26 '12 at 10:52
  • Non-thread-safe code is to me more "garbage" than thread-safe code. Anyway, it's moot since the op didn't define "low-garbage", and you and i are using our own definitions. It's my opinion that StackOverflow-answers should lean more towards safety than towards non-safety, otherwise inexperienced programmers will copy and paste unsafe examples. – Christoffer Hammarström Jun 26 '12 at 10:55
  • It is very rude to change other people's answers, especially in a case like this when you are just editing according to your preference and against my specific intent, and OP's specific request. Please roll it back and leave it alone. – Marko Topolnik Jun 26 '12 at 10:57
  • I saw the FAQ, but I fail to see your point in making me see it. – Marko Topolnik Jun 26 '12 at 10:59
  • The point is showing you it's not rude to change other people's answers. – Christoffer Hammarström Jun 26 '12 at 12:14
  • The FAQ states that you are **licensed** to edit other people's answers. No contention there. But, as a trusted SO user, it is your responsibility to make sure you are editing to improve -- and especially **you should never, ever change the central point of another person's answer** -- which is what you have done here. – Marko Topolnik Jun 26 '12 at 12:19
  • Even more so: you should never change the central point of **any answer that is already accepted** -- even if it's your own answer. That borders with vandalism. – Marko Topolnik Jun 26 '12 at 12:27
  • I did not change the central point of it. I changed it from non-thread-safe to thread-safe, as thread-safe code is usually superior. Nowhere was non-thread-safe code requested, you made that up. It was only a matter of moving one line, to make the code obviously better. Correct code is usually better than incorrect code with a disclaimer comment, especially on a site like StackOverflow where inexperienced programmers will copy and paste code without reading or understanding it carefully enough. – Christoffer Hammarström Jun 26 '12 at 12:40
  • Demonstrate where I made up that "non-thread-safe code was requested". – Marko Topolnik Jun 26 '12 at 12:44
  • You said "I specifically wrote that code to satisfy OP's requirement of being low-garbage", implying that OP's requirement of "low-garbage" meant "non-thread-safe". Nowhere did the OP request "non-thread-safe" or any variation thereof, but you say that that's the "central point" of your answer. – Christoffer Hammarström Jun 26 '12 at 12:45
  • The implication is entirely yours. I wrote low-garbage code which happened to be non-thread-safe. OP did not specify thread safety as a concern at all. – Marko Topolnik Jun 26 '12 at 12:52
  • You said i changed the "central point" of your code, when all i did was move one line to make it thread-safe. So the code being non-thread-safe is obviously important to you. – Christoffer Hammarström Jun 26 '12 at 12:54
  • After your edit each call allocates a new `Calendar` instance from the heap that turns into garbage on method return. The central point of my answer is, let's quote OP on this, "a fast, low-garbage" solution. – Marko Topolnik Jun 26 '12 at 12:56
  • Fair enough, each call would create one `Calendar` instance that is immediately garbage. But then you create an unnecessary `int[]` array instance per call when the calling code is only interested in the values inside, so the array becomes garbage. Replace the array with returning the calendar object and we've fixed both problems, and have thread-safe code. On another note, this whole thing reeks of premature optimization. The garbage object instance is usually immediately reused by the JVM anyway for almost no cost. – Christoffer Hammarström Jun 26 '12 at 13:05
  • The array is not garbage and is the most memory-efficient way to return a tuple in Java. Returning `Calendar` is out of the question because that burdens the caller with its unwieldy API. Notice that it would be incorrect to return the singleton Calendar as it is shared between all method calls. The best way to achieve thread-safety with the least performance impact is a ThreadLocal. However, without a specific request for thread safety, this is uncalled for and against the "fast" requirement, not to mention all the extra code needed. You are welcome to edit YOUR answer to your liking, however – Marko Topolnik Jun 26 '12 at 13:12
  • Obviously the array is garbage after the values inside are extracted. And obviously i meant to create a new instance of `Calendar` for each call which would replace creating one instance of `int[]` for each call. That would in total create one fewer object instances than your code, and be thread-safe to boot. Also, `int hour = calendar.get(HOUR_OF_DAY)` is better API than `int hour = array[3]`, not to mention that you can use a `Calendar` object for other API:s, for example `DateFormat`. – Christoffer Hammarström Jun 26 '12 at 13:17
  • When that array becomes garbage is up to the caller. As for API preference, you and I are both free to have our own preferences. As for "one fewer object instance", that is impossible since my code creates a total of one object per call. – Marko Topolnik Jun 26 '12 at 13:19
  • It will become garbage eventually, so you've won nothing, except you've lost thread safety and an object that's useful for other API:s. And `new int[]` creates one int array object instance, so that's one object instance per call. Arrays are objects, you know. – Christoffer Hammarström Jun 26 '12 at 13:20
  • See http://stackoverflow.com/questions/2009210/in-java-why-are-arrays-objects-are-there-any-specific-reasons – Christoffer Hammarström Jun 26 '12 at 13:24
  • Also, you create the singleton calendar, that is one extra object. – Christoffer Hammarström Jun 26 '12 at 13:25
  • Improved the code with a method that creates zero objects per call. – Marko Topolnik Jun 26 '12 at 13:50
  • Improved to a solution that makes thread safety achievable without hurting the fast and low-garbage requirement, but leaves it as a responsibility of the client. – Marko Topolnik Jun 26 '12 at 14:02
  • @ChristofferHammarström I've just completed a memory test, you may find the results interesting. A `Calendar` instance takes 448 bytes and an `int[3]` takes 32 (64-bit HotSpot on OS X). – Marko Topolnik Jun 26 '12 at 20:00
  • @downvoter How about leaving a comment on what you think is wrong with the answer. Especially since it has been improved several times and has been made by now into quite a good answer. – Marko Topolnik Jun 26 '12 at 20:39
0

java.time

As of Java 8 and later, the built-in class to use is Instant from the java.time framework.

Instant instant = Instant.ofEpochSecond ( 1_469_168_058L );

Dump to console.

System.out.println ( "instant: " + instant );

instant: 2016-07-22T06:14:18Z

Performance

I do not know exactly how java.time.Instant performs in terms of speed-of-execution or garbage-production. But you should test against this class. In my perusal of the source code in Java 9, it looks pretty simple and fast.

With a few method jumps, it basically just assigns a pair of integers, (a) number of seconds from epoch (a 64-bit long) and (b) a count of nanoseconds as the fraction of a second (a 32-bit int), after doing a couple of quick checks:

First looks for values of zero in which case it returns a static instance for the epoch itself.

if ((seconds | nanoOfSecond) == 0) {
    return EPOCH;
}

Secondly does a sanity-check on the number of seconds against the pair of min/max constants.

if (seconds < MIN_SECOND || seconds > MAX_SECOND) {
    throw new DateTimeException("Instant exceeds minimum or maximum instant");
}

Then calls the constructor, which assigns the pair of integer values to a pair of member variables (long and int primitives respectively).

this.seconds = epochSecond;
this.nanos = nanos;

Of course that is just construction. Interrogating for parts such as time-of-day means more work. As does generating a String via the toString method which involves another class, a DateTimeFormatter. The toString source code is one line.

return DateTimeFormatter.ISO_INSTANT.format(this);

And remember that if you want parts such as year, month, day-of-month, hour, and so forth in a time zone other than UTC, that means more work involving ZoneId and ZonedDateTime classes. For example:

ZoneId zoneId = ZoneId.of( "America/Montreal" );
ZonedDateTime zdt = instant.atZone( zoneId );
Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154